Ehm. Shared hosting was a thing since forever. VPS also existed.

Linode definitely had something along those lines.

Amazon won on APIs and overall integration but VMs were around already.

I remember the story really well as this is when i joined the workforce as a young GNU/Linux fan.