Back at that time, Microsoft provided programming languages (Basic, Fortran, Cobol and the like) for 8-bit machines, while the most-widespread operating system CP/M came from Digital Research. The two companies had an unspoken agreement on not raiding the other one's market. But Microsoft had licensed CP/M for a very successful hardware product at that time - the so called SoftCard for the Apple II. SoftCard contained a Zilog Z80 processor, and allowed Apple II owners to run CP/M and CP/M applications.
IBM - awakened by Apple's microcomputer success with the Apple II - approached Microsoft in search of an operating system and programming languages for their "Project Chess" = "Acorn" = "IBM PC" machine, which was to be a microcomputer based on open standards and off-the-self parts. Those off-the-self parts included Intel's 8088 CPU, a downsized 8086. One exception was the BIOS chip, which was reverse-engineered later by Compaq and others.
The legend goes that IBM's decision makers mistakenly thought CP/M originated from Microsoft, but that sounds doubtful. Anyway, Bill Gates told IBM they would have to talk to Digital Research, and even organized an appointment with Digital Research CEO Gary Kildall.
Kildall was a brilliant computer scientist, but probably missing the business instinct and restless ambition of Bill Gates. Some people say Gates didn't inform Kildall about who the prospective customer was, but only noted that "those guys are important", which might be plausible, as IBM was paranoid about anyone getting to know what they were doing. On the other hand, Gates himself once mentioned in an interview that Kildall knew it was IBM who was coming.
|Digital Research's former headquarters, Pacific Grove, California|
Again, different versions exist about that part of the story - one of them goes that Kildall actually appeared in the afternoon, but no agreement was reached either. Another problem at that time was that Digital Research had not even finished CP/M's 16bit 8086-version.
When IBM returned to Microsoft still looking for an operating system, Gates would not neglect that opportunity. Microsoft co-founder Paul Allen knew of a 16-bit CP/M clone named "Quick and Dirty Operating System" (QDOS), written by Tim Paterson of nearby "Seattle Computer Products". Paterson had grown tired of waiting for CP/M-8086, so he had decided to build one on his own. In a matchless deal, Microsoft purchased QDOS for a mere USD 50,000, and transformed it into PC DOS 1.0. IBM had unexclusively licensed DOS, which opened doors for Microsoft to sell MS DOS (back then slightly varying versions) to every PC clonemaker that would come along.
At the same time, Digital Research finally finished their 16-bit CP/M, which was even offered by IBM as an alternative to DOS, but never took off mainly because of pricing reasons (USD 240 for CP/M in comparison to USD 40 for DOS). Thanks to the similarities between DOS and CP/M, CP/M applications were easily ported to DOS as well - sometimes it was enough to change a single byte value in the program's header section.
Back then IBM still believed that even on the microcomputer market, profits would stem from hardware sales, not from software sales (remember they gave operating system and standard applications away for free in order to sell mainframes - software was a by-product). Their next mistake was to open doors to clonemakers thanks to their open-standards approach and their licensing agreement with Microsoft. IBM also paid a high price later during their OS/2 cooperation with then-strengthened Microsoft, when Microsoft suddenly dropped OS/2 in favor of Windows.
Myths entwine around the real events, and a lot of wrong or over-simplified versions are circulating. People tend to forget that Microsoft was quite successful long before the days of DOS, selling their Basic version, which ran on more or less every 8-bit microcomputer. They actually began in 1975 on the famous Altair. And no, Gates and Allen did not start their company in a garage (those were Steve Jobs and Steve Wozniak with Apple), they established Microsoft in Albuquerque, New Mexico - because that was where Altair producer MITS had its headquarters. Some years later they moved back to their hometown Seattle.
One of my college teachers once told us that "IBM came to Seattle to talk to an OS vendor, but those guys were out of town, so they went to Microsoft instead". Isn't the real story so much more amazing than that oversimplified one?
Update 2016: I found this Tom Rolander interview, who actually "went flying with Gary" that fateful day (at 17min 7sec):
In 2015 I held this presentation on the "History of the PC" at Techplauscherl in Linz: