In my mind, "the cloud" came into existence when it became practical to rent servers (virtual or physical) by the hour, rather than by the month.

It's one of those things where a difference in degree in implementation terms (leasing in smaller time increments) allowed a difference in kind in usage terms (on-demand server allocation over advance provisioning).