(FORTUNE Magazine) – MICROSOFT WAS ALREADY MONTHS INTO A MASSIVE project aimed at taking down Google when the truth began to dawn on Bill Gates. It was December 2003. He was poking around on the Google company website and came across a help-wanted page with descriptions of all the open jobs at Google. Why, he wondered, were the qualifications for so many of them identical to Microsoft job specs? Google was a web search business, yet here on the screen were postings for engineers with backgrounds that had nothing to do with search and everything to do with Microsoft's core business--people trained in things like operating-system design, compiler optimization, and distributed-systems architecture. Gates wondered whether Microsoft might be facing much more than a war in search. An e-mail he sent to a handful of execs that day said, in effect, "We have to watch these guys. It looks like they are building something to compete with us."

He sure got that right. Today Google isn't just a hugely successful search engine; it has morphed into a software company and is emerging as a major threat to Microsoft's dominance. You can use Google software with any Internet browser to search the web and your desktop for just about anything; send and store up to two gigabytes of e-mail via Gmail (Hotmail, Microsoft's rival free e-mail service, offers 250 megabytes, a fraction of that); manage, edit, and send digital photographs using Google's Picasa software, easily the best PC photo software out there; and, through Google's Blogger, create, post online, and print formatted documents--all without applications from Microsoft.

While Google was launching those products--all of them free--Microsoft has been trying in vain to catch up in search. It has spent about $150 million on its search project, code-named Underdog. But Google and lately Yahoo keep leaping ahead with innovations like local-area search complete with maps and satellite photos, ways to search inside a video file, and search designed for cellphones.

Simply put, Google has become a new kind of foe, and that's what has Gates so riled. It has combined software innovation with a brand-new Internet business model--and it wounds Gates' pride that he didn't get there first. Since Google doesn't sell its search products (it makes its money from the ads that accompany its search results), Microsoft can't muscle it out of the marketplace the way it did rivals like Netscape. But what really bothers Gates is that Google is gaining the ability to attack the very core of Microsoft's franchise--control over what users do first when they turn on their computers.

Google co-founders Sergey Brin and Larry Page and CEO Eric Schmidt all say that any talk about supplanting Microsoft is ludicrous. But the idea that Google will one day marginalize Microsoft's operating system and bypass Windows applications is already starting to become reality. The most paranoid people at Microsoft even think "Google Office" is inevitable. Google is taking over operating system features too, like desktop search. There are fewer uses for the START button in Windows now that Google's desktop search can locate any program, document, photo, music file, or e-mail on a computer.

All of which helps explain why inside Microsoft, the battle with Google has become far more than a fight over search: It's a certifiable grudge match for king of the hill in high tech. "Google is interesting not just because of web search, but because they're going to try to take that and use it to get into other parts of software," says Gates as he leans forward in his chair, his body coiled as if he could spring to his feet at any second. "If all there was was search, you really shouldn't care so much about it. It's because they are a software company," he says. "In that sense," he adds later, "they are more like us than anyone else we have ever competed with."

Though CEO Steve Ballmer has been boss for five years, Gates, who is chairman and chief software architect, is leading the charge against Google. Forced to watch Google's stock soar the way Microsoft's used to, and Brin and Page enjoy their roles as tech's new rock stars, Gates brings to the fight a ferocity that nobody has seen since the Netscape war a decade ago. Their popularity gets under his skin. "There's companies that are just so cool that you just can't even deal with it," he says sarcastically, suggesting that Google is nothing more than the latest fad, adding, "At least they know to wear black."

Just how big is Microsoft's Google problem? First, a reality check: Microsoft, with nearly $40 billion in revenues, is ten times the size of Google. It's sitting on $34 billion in cash, generating $1 billion in new cash a month, and, thanks to its core Windows, Office, and server products, growing at 15% a year, with operating margins above 30%. Most companies would love to have such numbers.

But Microsoft isn't exactly in fighting trim. Its ambitious new operating system, code-named Longhorn, is more than a year late, even after having been scaled back. Linux, the free operating system that Gates once scoffed at, is fighting Microsoft for share in both the server and desktop markets, forcing the company to do the unthinkable: offer customer discounts. Last year it had to spend $1 billion to rewrite thousands of lines of code to make its programs less susceptible to viruses. Its Xbox gaming console is winning raves from players but has yet to make serious money. Meanwhile, Apple has stolen the show in online music with its hugely popular iPod and iTunes Music Store. Plus, the recently released Firefox browser, which can be downloaded free, has forced Gates to reconstitute an Internet Explorer development team. Indeed, four years have passed since Microsoft released a piece of software that generated the kind of buzz Google seems to generate every month.

Dozens of current and former Microsofties say that Google's success is causing a corporate identity crisis. Gates basically created the notion that success in software is a function of the IQ of your team, and for years Microsoft has prided itself on having the smartest employees on the planet. Now many of those overachievers feel as though they've gotten their first B. Google, not Microsoft, is the hot place to work for young engineers. Every month it seems as if Google hires away one of Microsoft's top developers. Before Google's IPO last fall, Microsoft executives dismissed this brain drain as a function of greed. But when the exodus continued after the IPO--especially when Marc Lucovsky, one of the chief architects of Windows, bolted for Google--it was clear that Microsoft had a bigger problem on its hands. As of March, roughly 100 Microsofties had left for its search nemesis.

Google has even had the nerve to set up an office five miles down the road from Microsoft's Redmond, Wash., headquarters. Its opening last November was supposed to be an invitation-only affair, but word spread and by 7 P.M. The place was swarming with dozens of uninvited Microsofties--casually, and sometimes not so casually, looking for work.  The Google migration has gotten so bad, says a former Microsoft employee, that when he told his bosses and colleagues he was leaving earlier this year, "the first question out of their mouths was 'You're not going to Google, are you?'" (He was not.)

Perhaps worst of all, Google is building programs that people at Microsoft prefer to their own.  Microsofties have always been voracious samplers of competitors' products; many used the Netscape browser for years until Microsoft's Internet Explorer was good enough.  But today, stop almost anyone on campus and ask which e-mail or photo or blogging program he uses, and the answer will invariably be Google's.  No wonder Bill Gates is mad.

To understand why Microsoft is having so much trouble catching Google, it helps to hear the story of Chris Payne. He had been watching Google closely for months by the time he got Gates' ear in February 2003. A newly minted vice president charged with overseeing a grab bag of web products for MSN, Microsoft's web portal, Payne stepped to a podium in the conference room in building 36 at the Redmond campus. Peering at his audience--Gates, Ballmer, and about two dozen other Microsoft brass--he launched into the most important pitch of his career. He asked them to approve a massive push into the search business--a Google killer.

Payne, 37, was nervous but pumped. Although Ballmer was present, everyone knew no big technology project got a green light without Gates' say-so--and the chairman never said yes until he had subjected the idea to a withering barrage of questions. Zapping through PowerPoint slides, Payne spoke for two hours, showing in painstaking detail how MSN was making a monumental mistake outsourcing its search function to third parties. In those days Inktomi, a small firm that had agreed to sell itself to Yahoo in December 2002, provided MSN's search results. Overture, a brainchild of Idealab's Bill Gross, supplied the ads to go alongside them. In hindsight, outsourcing search looks dumb, but back then, search was widely viewed as a money loser. Payne explained how Google was developing a great search engine, and how its minimalist design and consistently relevant results--better than those delivered by MSN's cluttered site--were attracting legions of Internet users. Worse, Google had unlocked the secret of online advertising; its automated system noted a user's search request and then delivered discrete matching ads alongside the results. That enabled the Internet upstart to generate gobs of cash. The impact on MSN was obvious. "I'm seeing revenue in the category go up, and I'm seeing our market share go down," Payne said later.

Payne told Gates & Co. that he would need more than $100 million and 18 months to build his search engine; that he wanted the authority to pull the cream of Microsoft's brainiacs into the effort. And Gates? He asked almost no questions, interrupting mostly to suggest people in Microsoft who might help. "It was reasonably obvious to me that we were going to have to depend on ourselves, not our partners, for search," says Gates now. So when Payne finished, Gates signed off on one of the largest commitments for a new business in Microsoft history: Project Underdog was born. Payne could hardly contain himself. "I was very, like, God!" he says, pumping his fist. "I had done all this work, and then I'm like, 'He said yes!' Honestly, it was awesome."

It was the last easy win for Payne. Last November he released Microsoft's search engine, followed in December by a desktop-search tool (two months behind Google) and in March by a search-related advertising business. Microsoft supported the launches with a $150 million ad campaign and scores of other promotions. But the effort has generated little buzz so far, and Microsoft's global market share, at about 13% of search requests, remains puny.

Yet Payne seems impervious. A gregarious Kentuckian with a devilish Jim Carrey smile, he talks in wide-eyed bursts. He seems to be in motion even when he's at rest. Since taking charge of the search effort, he has become well known within the company not just for energy and charisma but also for toughness. Gates may have given him a pass during that initial presentation, but Payne has been at the receiving end of plenty of vicious tongue-lashings since then, during his monthly meetings with Gates and in the weekly e-mails he receives from his boss.

Payne joined Microsoft right out of Dartmouth in 1990, eventually ending up as a marketer and strategic planner for the company's database-software business. His first break came in 1995 when he was transferred to the then-fledgling MSN division. He was one of the original three employees on MSN Investor, playing a critical part in making it one of the best financial websites. But he didn't stick around to reap the rewards. He jumped to Amazon in 1999, only to discover that working there was more about retailing and merchandising than he had thought it would be--he missed building and selling software. By early 2002 he was back at MSN, running its home page and search, among other things. Over the course of that year, he saw Google's threat and began formulating the plan for Underdog.

The project's beginnings were auspicious. With Gates' backing, Payne recruited top talent throughout the organization, like Ken Moss, whom he brought in as chief engineer. Moss had been instrumental in the early 1990s in creating Excel, Microsoft's spreadsheet program. The fledgling search unit quickly grew to roughly 500 engineers and marketers. Nevertheless, it successfully cultivated a startup--even renegade--mentality. Payne's managers bragged to underlings that they had the clout to poach anyone inside Microsoft. And the focus was on winning--in the halls near Payne's office, the walls were covered with performance reports on the group's servers, comments from customers on how Microsoft could improve, and media clippings about Google.

For six months the team even bought its own servers. Gaining clearance to run and monitor the project on the corporate server farm would have been too time-consuming, Payne's team felt--not to mention the strain an ambitious search offering would put on the systems. (Google is widely estimated to run 250,000 servers to support its search.) The technology they eventually unveiled used a heavily modified version of the Windows server operating system. All its other components were of their own design, run with a lot of software they had written themselves.

Confidence ran high. A senior Microsoft executive said the top brass thought the fight against Google "was going to be Netscape all over again." Microsoft has a long, dramatic history of being a fast follower, rarely first in a market but ultimately providing the most accessible and practical solution, then outmarketing competitors. The company hasn't always played by the rules, but when it has gone after a market, it has done so quickly and aggressively. Current and former executives of companies like Apple, WordPerfect, Lotus, Novell, and of course Netscape can attest to that.

Like Google, Netscape threatened to sideline Microsoft's operating system, in its case with the web browser that founder Marc Andreessen unveiled in 1994. The reason was that the browser, which cost each user $39.95, would enable applications like word processors and spreadsheets to reside on centralized Internet servers rather than on the hard drives of users' desktops. That in turn would lessen their need for Windows or Office, sapping Microsoft's business. But Gates rallied Microsoft to develop its own browser, which it then bundled free with Windows. Netscape's market share collapsed, and the upstart was forced to sell to AOL (like FORTUNE's publisher, a unit of Time Warner) three years later.

Trying to build a Google killer, however, has turned out to be truly humbling for Microsoft. The effort has taken longer, cost more money, and exposed more big-company problems at Microsoft than anyone imagined. As Payne predicted, targeted online advertising has indeed become a gold mine. Still in its infancy, it's one of the hottest sectors in high tech, a $5-billion-a-year market growing at some 40% annually. Yet no matter what Payne and his crew do, Google and Yahoo seem to do better. "I remember when [Payne's team] showed off their first prototype in early 2004--people laughed because it was so much like Google," says a former Microsoft executive. "We had copied them. That's not how you lead."

A headache for Payne is that Microsoft isn't as nimble as smaller, younger rivals like Google and Yahoo. For example, at Google, engineers are responsible for the software that they write--period. They don't hand it off to a "system operations" team to deal with bugs. When something goes awry, the team that wrote the software and knows it best is responsible for fixing it.

The bureaucracy and even Gates himself have gotten in Payne's way. Underdog has been slowed by turf battles within MSN and among the company's six other business units. Microsoft executives' compensation is based on the success of their own organizations, which means, says a former exec, that every interaction Payne's team has with, say, the Windows business unit comes with strings attached. Payne and his team have tried to speed development by buying their way into the search game, but something has always thwarted that approach. In spring 2003, Payne pitched Gates on buying Overture, a move that would have given Microsoft search engine technology out of AltaVista as well as an advertising business that was generating huge profits. But Gates shot the plan down, convinced that Microsoft could do a better job for less money on its own. Instead, Yahoo bought Overture, a move that, together with its earlier purchase of Inktomi, enabled it to catapult itself successfully into the search game in a year.

In fall 2003, Microsoft briefly considered buying Google, only to realize that even if Brin, Page, and their board could have been persuaded to sell--which seemed unlikely--Microsoft would have been left to explain to the world why it was now running a search engine built entirely on Linux instead of Windows. Even when it did buy a company--Lookout--in June 2004 (Lookout had mastered fast Outlook e-mail search), it didn't move quickly enough to expand the software to search the whole desktop.

The price for being slow-footed became abundantly clear last fall: Google beat Microsoft to market with desktop-search software by two months. The news ripped through Microsoft with titanic force. Everyone from Gates on down scrambled into meetings to assess how good Google's product was. Not especially, they decided. Even so, it dealt a blow to their pride. "Here Microsoft was spending $600 million a year in R&D for MSN, $1 billion a year for Office, and $1 billion a year for Windows, and Google gets desktop search out before us? It was a real wake-up call," says an exec. "It was the first time many people in the corporation understood that Google was more than just a search engine. People said, 'If they can do desktop search, what prevents them from doing a version of Excel, PowerPoint, or Word, or buying Star Office [from Sun Microsystems]?' "

What does Google make of Microsoft's growing animosity and paranoia? Although neither the co-founders nor CEO Schmidt would comment for this story, Schmidt told an audience of Internet pioneers at UCLA last fall, "One of the criticisms that the media makes is to compare Google to previous-generation companies. Google is trying to solve the next problem, not the last problem." Privately, Google's executives understand exactly the impact they are having on Gates and his team. They project a carefree image in part because it makes business sense. One blunder by Netscape was that it let Andreessen tell the world how he intended to put Microsoft out of business. Count on Google not to repeat that mistake.

Remember, many of the most influential people at Google are hardened Microsoft warriors. Schmidt battled Gates as CTO of Sun Microsystems and CEO of Novell in the 1990s. Omid Kordestani, Google's head of ad sales, was a top executive at Netscape. Three of Google's directors, Ram Shriram, John Doerr, and Michael Moritz, have been on the front lines of Silicon Valley's war with Microsoft over the years. "Microsoft can literally spend a billion dollars on this if they choose. We take them very seriously," says a Google executive. One reason Google has been rolling out so many new or improved products is that Schmidt understands that innovation is the only sure edge Google has. The moment Google allows itself to slow, Microsoft could overwhelm it.

FOR ANYONE WHO HAS BEEN WATCHING GATES OVER THE years, the idea that an upstart like Google could so flummox him and his fierce company takes getting used to. But Google is a rival unlike any he has faced in a long time. In previous battles, Microsoft always had a powerful trump card: It controlled the Windows operating system. That meant that when consumers bought a PC, Microsoft had a powerful say in what products and services they saw first. It had pricing power and distribution power over competitors. Because of that, its applications didn't have to be superior to those of the competition--just roughly equal. Windows wasn't better than the Macintosh; Word didn't improve on WordPerfect, or Excel on Lotus. Even Explorer was only as good as Netscape. Microsoft's genius was integrating them seamlessly to make them easier for customers to default to, and then using its marketing, distribution, and pricing clout. It won by attacking competitors' business models, not their technology.

Microsoft's array of weapons has so far proved next to useless against Google. For one thing, any attempt to bundle search with its products will probably be scrutinized by antitrust regulators. Meanwhile, you no longer need a PC to use Google--it works fine from a Treo, a BlackBerry, a cellphone, a television, an Apple, or a Linux computer--any device with some kind of keyboard and Internet access. Nor can Microsoft undercut the price of Google software as it did with Netscape: Google is already free. There's no quick and easy way to lure away Google's online advertisers either. They pay based on the price of a keyword in a search and on how many times users click on the ad, but Google doesn't control that--it's set by auction. Says a former Microsoft executive: "Microsoft can play its old game to compete with Linux and Apple. It has to play Google's game to compete with Google."

Gates and Payne don't agree at all. To them, beating Google is the same as beating any of Microsoft's previous challengers. It's still about writing software that is easier to use, and the easiest-to-use software is always the kind that's integrated with what people already have--like Windows or MSN. Gates says that when Microsoft is done integrating search into future versions of Windows and Office, the world will look back at the way we are now "Googling" for stuff on the Internet and laugh. "The idea that you type in these words [in the search box] that aren't sentences and you don't get any answers--you just get back all these things you have to click on--that is so antiquated," he says, later adding, "We need to take search way beyond how people think of it today and just have it be naturally available, based on the task they want to do." For example, if you wanted to look up a factoid while you were writing a document, you might search for it without ever leaving Word.

Perhaps Gates is right--again. After all, Google may be hugely profitable and a Wall Street darling, but it is also a young company, largely controlled by its founders and dealing with the unavoidable pains of torrid growth. Oddsmakers would say the likelihood of its stumbling is high, and no one is better at outlasting the competition than Gates. Certainly the search game is still in its infancy. Only a fraction of the content available online is actually searchable. For instance, even subscribers can't search current and archived issues of the Wall Street Journal or most other publications with a search engine; you have to go to the publication's site. This suggests that the search engine that can get the world to list premium content on its platform will have a leg up on the competition. Microsoft has plenty of money to buy the rights to such content; it also owns powerful digital-rights-management software, which helps copyright holders control who uses their products and how often. Those should be advantages in negotiations with companies worried about losing control of copyrighted text, music, and video on the Net.

Another advantage for Gates & Co. is that search engines are still technologically primitive. They can't understand context, for example; if you type "chip," they can't tell whether you are looking for a snack food or high-tech equipment. As a result all three big search engines are scrambling to find ways to make search more personalized. The thinking is that the more a search engine knows about who is searching, the more accurate the results will be. Each company has the foundations of such a product in its desktop-search software, which can tell what you have on your hard drive. Perhaps Microsoft, because it understands Windows better than any other company, will be able to offer faster, more accurate searches.

All the same, Microsoft is taking longer to catch Google than anyone could have imagined--and it will take longer still. Unless it can deliver search that is plainly better, most users won't bother to switch, says Piper Jaffray analyst Safa Rashtchy. He adds, "Google is a huge brand. From where I sit, it's their game to lose." The competition could well test Gates' patience as never before. In spring 2003 he told one of his executives, "These Google guys, they want to be billionaires and rock stars and go to conferences and all that. Let's see if they still want to run the business in two or three years." Well, two years have passed, and so far, they sure do. ■

FEEDBACK fvogelstein@fortunemail.com