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.