>3.6
It was an implementation detail in 3.6, 3.7 made it part of the language spec.
Which is good, can finally get rid of the metaclass I hacked together for my spark (earley parser that used to be used in the python build process to parse ASDL) shenanigans.
First implemented in pypy, then ported to cpython 3.6.
Talk by Raimond Hettinger about the new implementation with several other implementations:
The rationale is that even if they clearly said "we might make this non-sorted again later", in practice too much code would end up relying on the new behaviour (whether by accident or because people didn't pay attention to the warning).
So if changing the behaviour is likely to become impractical anyway, they might as well make it a promise so people can benefit from the guarantee.
They made essentially the same choice when they changed sort() to an algorithm that happened to be stable, about 15 years ago.
After you have used it for a while, it is a great feature. I would now be happy to take a small dict performance hit in order to preserve the ordering guarantee.