In 1996, two geeks that nobody had heard of in a PhD program had to quickly find decent research papers for their thesis. Digitized research papers were just arriving at the brink of possibility.
They had to read every paper to find good ones. "This is too painful" they thought. So they stopped researching manually. Instead, they wrote a recursive program to rank research papers based on the ranking of other research papers citing them in their footnotes. This way, they could quickly find "decent" ones. Their names were Larry Page and Sergei Brin. When the Internet took off, they repurposed the program to find "decent" web pages instead, based on the decent-ness of other pages citing them via hyperlinks. And they named the program "Google". 
In 1998, they raised $100K in angel funding from the cofounder of Sun Microsystems and a matched amount from a Stanford Professor to improve the patentable technology, and incorporated as a company. The workload was mounting up too quickly. By 1999, they decided that Google was distracting them too much from their studies, and attempted to sell it for $1 million to get their angel investors' money back. They went to Excite (a successful search company), which negotiated their deal down to $750K and then backed out.  Yahoo!, one of the billionaire empires of the dot com era, was given a chance to buy Google for $1M.
Yahoo, already making massive revenue in Internet webpage categorization, didn't think search was going to ever be profitable. They wanted people to spend lots of time on Yahoo content and ads, not exit quickly to their search destination page. So they passed on the offer to buy or exclusively license Google search technology in its infancy. Google, wanting to return its investor's money, was forced to escalate its commitment. They raised $25M from top VCs in Silicon Valley later in 1999. With the funding they started hiring brilliant engineers, including Google's first female engineer and employee #20, Marissa Mayer. She joined Google to invent the future, despite having much more prestigious (and probably better paid) offers at Carnegie Mellon and McKinsey.
The Internet grew exponentially, creating a stock market bubble that burst on March 2000. Yahoo! failed to keep pace with website categorization ("this is too painful" they thought), so they signed a partnership deal with Google to provide search. As the 2000 dot com bust was killing all startups, Yahoo was saving Google's life for selfish reasons. Google became a post-bubble startup.
To rid itself of dependence on Google, between 2000 and 2004 Yahoo started buying up all sorts of small search companies and integrating them into its services. In 2002, Yahoo! acquisition office estimated to be able to convince Google to sell for $5 billion. But Yahoo's new CEO thought that would amount to a speculative capitulation, especially in light of the exuberance leading to the dot com bust in his rear view mirror. "Google is worth no more than $3 billion, if that!" he argued (with some curse words in there). He decided to bet against Google and on all its enemies. By 2004, Yahoo ended its partnership with Google. That year, Google went public (IPO) to be able to raise the money to keep going.
The darkest moments that Google experienced were mostly due to its rapid growth. In the process of scaling its culture, several times it had near-death experiences. Most of these had to do with maintaining communication lines in an organization that went from 2 individuals to several thousand within the course of a handful of years. Larry and Sergei were surprised to find, on the contrary to their predictions, that scaling free food and themed offices was the easy part; the difficulty of scaling employee motivation and communication led to having to change Google's CEO from Larry Page to Eric Schmidt, the tentative "adult supervision".
Google started battling on multiple fronts with Yahoo. Not only it lured cash-cow advertisers away, but it also invented Gmail and started offering free email inboxes that were 1GB each, or 250 times larger than what Yahoo was offering. Users defected to Google in droves, with all their ad-targetable personal data. "This is painful", they thought, when they couldn't find their favorite page or email on Yahoo. And Yahoo, which was still betting on content viewership more than personalized search, started playing catch up.
The temptation to put advertiser interests before users was naturally a strong force. Fortunately for Google, their rapid rise (thanks to the initial partnership deal with Yahoo) had maintained more control in the hands of the founders than the investors. One of the employees came up with the value statement "Don't be evil" during the IPO year, and it stuck.
For the next eight years, Google became what investors had wanted the year 2000 to be: the promise of the Internet. In 2012, Google's market cap exceeded that of Microsoft at $248 Billion, making Google the second-highest valued technology company in the world behind Apple. That same year, Google's first female engineer, Marissa Mayer, was tapped to replace the CEO of a struggling company, Yahoo. The capitulation of the incumbent was finally complete.
Knowing where its arch enemy went wrong, from the beginning Google put a strong merger and acquisition program in place to identify and buy startups that could become a potential threat to it. It has shown very little bias about the size of the opportunities, buying startups as small as a few founders to companies as large as the $12.5 billion Motorola Mobility. (Not buying Facebook was a notable miss, which I've previously written about in a different story.)
But history judges the most visionary investment of all to be the $100K check that Andy Bechtolsheim wrote in 1998 (matched by one of equal amount written by his friend, Waterloo-educated Stanford Professor of Computer Science David Cheriton). Andy, a Bavarian-born entrepreneur and co-founder of Sun Microsystems, made out the check to "Google Inc." before Larry and Sergei got the chance to incorporate the company. All four knew each other while independently inventing the future at Stanford. Each one of those checks, by my calculation, are worth nearly $6 Billion today.
That's more money, sitting now in Andy's bank account, than Yahoo's fully-informed CEO was willing to spend to save his entire empire.
Even the emperors of our time predict the future incorrectly. To make the right investment in the future, you must be among its inventors.
- Examining the Birth of Google - Interview with Terry Winograd, Larry Page's professor in Stanford. Harvester Blog by Saqib Rasool
- Google Financing in 1998 and Initial Public Offering in 2004
- The Google Story: In 1997, Yahoo turned down Google.