FORTUNE — Bill Gates was the star attraction at a private event that included some of Silicon Valley’s young luminaries in San Francisco last October, but his planned topic, philanthropy, wasn’t the most prominent topic on their minds. Seven weeks earlier, Microsoft (MSFT) CEO Steve Ballmer had abruptly announced he would step down within 12 months, just as soon as a successor could be found. Gates was interviewed in front of the group by famed venture capitalist Sir Michael Moritz, who politely stuck to the philanthropy script. But in many ways Moritz didn’t need to ask about the CEO search; everyone in the room already knew the process had become something of a circus.
This isn’t how it’s supposed to work. Microsoft is a corporate aristocrat, albeit an eccentric duke, for which succession should be smooth, non-controversial, and unsurprising. Instead, at least 17 candidates were publicly speculated upon; leaks from employees and some of the candidates themselves competed for advantage in the media; a few presumed candidates, some of whom may never have been candidates at all, publicly disclaimed interest in the job; and Isle of Man bookies offered odds on the eventual winner.
Even as Microsoft is poised to name a new CEO — it has been reported that the company will name insider Satya Nadella, head of its cloud and enterprise group — the process leading up to the announcement has emerged as, quite literally, a textbook example of how not to do CEO succession. (A forthcoming book by a management consultant, for example, will open with a long section on Microsoft’s CEO search. The chapter tentatively is called: “Getting It Wrong.”) More deeply, it exposes starkly how Microsoft is at a crossroads. As it struggles to be relevant in the contemporary information technology world of mobile devices, social media, video — in each of which it has failed so far — its structure, its strategy, even its titanium-strength culture are in play. Its new CEO will likely change them all.
The urgency of finding a new direction for Microsoft rose from orange to red just over a year ago. That’s when Ballmer met with Alan Mulally, Ford Motor Co.’s (F) savior CEO and an old friend, to talk about how to reorganize Microsoft. It’s also when Microsoft lead director John Thompson bluntly told Ballmer he was moving too slowly. “Hey, dude, let’s get on with it,” he said in a conference call, as he later told the Wall Street Journal. Ballmer said he’d move faster.
Then, last April, activist investor Jeffrey Ubben closed in. Ubben, CEO of San Francisco-based ValueAct, disclosed that he’d acquired a $2 billion stake in the company — a move that pushed Microsoft shares up, a sign that investors were rooting for the activist to spur change at the tech giant.
As the pressure for change intensified, Microsoft responded with a series of actions that each required months to arrange, yet which together seemed bafflingly uncoordinated and even conflicting. At 6 a.m. on July 11, Ballmer sent two companywide emails announcing a massive reorganization. Together the emails ran to nearly 6,000 words, but their message could be summarized in three words: Be like Apple.
Ballmer had correctly diagnosed Microsoft’s problem, a structure and culture in which divisions warred openly. By contrast, Apple had become the world’s most valuable company in part by integrating all parts of the business more deeply than any other company of its size. So Ballmer’s emails emphasized “focusing the whole company on a single strategy,” “working together,” “collaboration,” and “common goals.” They also made clear that Microsoft would now be highly centralized, with the CEO as central decision maker.
The changes rocked the company as 101,000 employees calculated their new allegiances in the CEO-centric structure. Just six weeks later their calculations were shredded by a new email from Ballmer. He was resigning.
The announcements produced a weird blend of chaos and paralysis inside Microsoft. Everything was changing, but with a new CEO on the way — no one knew who or when — why would anyone make significant decisions?
Then, one week after Ballmer said he’d be leaving, the company announced that Mason Morfit, president of Ubben’s ValueAct, would have “the option” of joining the board at the first regular meeting of 2014 — scheduled for March. It is unusual for any company to so cordially invite an activist investor on its board, and it was unprecedented for Microsoft, whose board has been dominated by Gates for its entire history.
Four days later, another earth-shaker: Microsoft said it would buy Nokia’s handset business for $7.4 billion. That was obviously a major strategic move by a lame-duck CEO, which raises all sorts of questions (questions we’ll get to in a moment) about the company Microsoft’s incoming chief will inherit.
Thus the stage was set, theater-of-the-absurd fashion, for the most avidly watched CEO search in years. The press seemed to suggest that the board was considering nearly every sitting CEO of a major enterprise tech company. Among those Fortune has confirmed as in the running: Tony Bates, a business development executive at Microsoft who joined the company in 2011 when the software company acquired Skype, and Vik Gundotra, a former Microsoft general manager who now runs social at Google.
Ford’s Mulally was the most famous of the many additional rumored candidates. Multiple sources say that he very much wanted the job, at least at first; who eventually spurned whom is in dispute, but he publicly took himself out of the running on Jan. 7. The major disagreement among directors, say multiple sources, was over what type of CEO Microsoft needs now. One faction favored a strong operating executive who could get this massive machine under control. The other faction wanted a tech visionary.
Microsoft’s CEO search marks the emotionally painful transition that every company must get through, moving from the founders’ guidance to a new generation of professional managers who weren’t present at the creation, and it isn’t easy. In recent years, for example, Nike, Dell, and Starbucks have all tried it and blown it; in each case the new CEO got fired, and the founder returned to right the ship. Microsoft can’t afford that scenario.
If Gates or Ballmer someday displaces the new CEO it would be seen as a monumental failure of management, pushing the company even further behind in the fast-changing tech sectors where it’s already a laggard. Nor can it afford an HP-style parade of wrong CEOs. The stakes are extremely high.
While practically no one disputes that Microsoft has lost its way, the company is far from desperate. This is not General Motors in 2009. Microsoft is still a spectacular performer, the seventh-most profitable company in America (earning $17 billion in fiscal 2013) and the seventh-most valuable, ahead of Chevron and IBM. Its return on capital exceeds its cost of capital by a staggering 40 percentage points, says the EVA Dimensions consulting firm, which is better than Apple (AAPL) or Google (GOOG).
But compared to those companies — and others, ranging from Samsung (SSNLF) to Salesforce.com (CRM) — Microsoft has struggled to convince investors and end-users that it can innovate and reinvent entire businesses. The company acknowledged that its reboots of the Windows operating system, Vista and Windows 8, were flawed, and its acquisition of Nokia’s handset business is an acknowledgement that its mobile strategy has flopped too. Its bright spot has been its cloud business, the one that presumed successor Nadella runs.
The new CEO must find a way to reenergize Microsoft, to have investors and consumers mention the company in the same breath as Apple and Google when they talk about innovation and especially future profit growth. He will have to motivate a whipsawed workforce, and may have to do so using a blueprint and assets put in motion by his predecessor. This won’t be an easy job. In the end, Microsoft seems to have chosen a CEO in the time it promised it would. But the messy, high-profile, loudly debated manner in which the search played out only amplifies the tough task ahead for the new chief executive.