[jabl]

OoO is a surprisingly old idea, first used in the IBM System/360 Model 91 released all the way back in 1966.

https://en.wikipedia.org/wiki/Tomasulo's_algorithm

Took a while until transistor budgets allowed it to be implemented in consumer microprocessors.

[twoodfin]

Also for the gap between CPU speed and memory speed to matter enough for it to be worthwhile.