The S3 stuff was kicked off in the late 90s and everyone just kinda-sorta said why? But it seems to have been the first modern cloud-type service.
Now, I personally hate the term "Cloud" because it's pretty meaningless, and you can look back throughout the entire history of computing and find examples of distributed, remote storage, compute power etc etc.
But if we're going to call anything "Cloud" in the sense we try to use it now, then I reckon Amazon were first to market by a mile.
“If computers of the kind I have advocated become the computers of the future, then computing may someday be organized as a public utility just as the telephone system is a public utility... The computer utility could become the basis of a new and important industry.”
— John McCarthy, speaking at the MIT Centennial in 1961
Although that was no doubt in part due to the extreme expense of computers then. He said that 4 years before Moore published his famous Moore's Law, which many refused to believe for decades, in a period when computers were transitioning from vaccume tubes to transitors, which cost many hundreds of dollars when adjusted for inflation, and probably still when they were shipped with serial numbers. And of course memory was still made by hand out of magnetic cores.
Multics was the result of this vision of McCarty and others at MIT, hence its strong focus on security.
Computer "service bureaus" offered outsourced computing services in the 1960's and 70's. Do some research on "Tymshare", for example, and you'll see that "the Cloud" was alive and well back in the 1960's.
The Wikipedia article is organized confusingly. It talks about the 2002 launch of "Amazon Web Services" which at the time was just an API for the Amazon retail catalog. Then for some reason it links to a press release about the 2009 release of "EC2 for Windows", then goes back to talk about earlier launches like MechTurk (2005), S3 (2006), and EC2 (2006). I'll see if I can clean up this mess... [Update: cleaned up the article and added some citations.]
Note: I worked at Amazon.com from 2005 to 2008, the period when the company launched its first cloud computing services.
Softlayer was ahead of amazon by about 6 months. They just didn't use the term cloud. Or in the founder's terms "We knew it was awesome, but we didn't have a name for it".
The prior strategy (meme) was called "grid computing".
AWS' strategy of virtualization honors interfaces (cut points) between the major OS and network stack functional areas.
Grid computing was about portable code running on compute farms, more like a time share. Like an app server.
I shamefully admit I was slow to grok AWS. I had been using VMware for testing and cohabitation and such for years. I just didn't see how AWS was any different, or better. I really missed the boat on this one.
This was my first take-away ... at least Wired linked to an article they wrote backing it up (even if you still don't agree): http://www.wired.com/2012/11/amazon-3/
That's a bit of a journalistic stretch.