On: Examining the silicon dies of the Intel 386 proces...

[bonzini]

Out of order execution was introduced in the Pentium Pro, the Pentium was already able to execute two instructions per cycle but was still in-order.

Note that this "magic" is mostly implemented not in microcode, but rather in hardwired logic.