By Kevin Maney, contributor

FORTUNE — In September 2009, Silver Lake Partners and venture firm Andreessen-Horowitz bought Skype from eBay, where it had become the Kurt Cobain of technology companies (wildly popular, deeply troubled). The value of that deal: $2.75 billion.

In May 2011 the new owners announced that they were selling the company to Microsoft for $8.5 billion.

Voilà! Six billion bucks in less than two years.

For many, the Skype deal is seen — along with exuberance for the LinkedIn IPO and sky-high private valuations of companies such as Facebook — as a sign of a fast-inflating technology bubble: What else could explain such a lofty price tag for a company that lost $7 million in 2010 and $418 million the year before? What could have changed in just two years to make Skype nearly three times as valuable?

A lot, according to the executives behind the transaction, who spoke with Fortune exclusively about the strategic and tactical moves they made to transform the company from a quirky Internet phone service into a sophisticated and growing voice and video communications app. Indeed, Skype had long-standing plans to go public, and its backers felt sure it would have thrived on its own. “We have occasional fantasies of calling up [Microsoft] and torpedoing the deal,” quips Marc Andreessen, founder of Andreessen-Horowitz. “I’m thrilled with the deal but would be equally thrilled if it fell apart.”

The key to fixing Skype, which eBay (EBAY) struggled to integrate into its auction site, was to win over the company’s mercurial founders, Niklas Zennström and Janus Friis, who actually owned the rights to the software underlying the service — without that intellectual property, it would be impossible to unleash Skype’s potential. The problem: The two had been pushed aside after the eBay acquisition and had no intention of throwing a bone to the next guys who wanted to buy their invention. In fact, the moment Silver Lake floated a buyout offer, Zennström, a Swede, and Friis, a Dane, sued all the parties involved.

Egon Durban, the Silver Lake partner who was leading the transaction, realized he needed help with the founders. Enter Andreessen, himself a founder (Netscape, Opsware), an eBay and Facebook board member, and a guru to a new generation of tech entrepreneurs. To Andreessen, Skype was a potential gem — one of the few great network-effect tech companies ever created.

Andreessen agreed to invest $50 million of his venture firm’s money in the deal on the bold assumption that he and Durban ultimately would win the founders’ trust. He assumed correctly: Zennström and Friis accepted a 14% stake in the new ownership structure in exchange for giving all the IP back to Skype. With Skype’s software rights secured, the investors went into turnaround mode. Durban, who says he spent about half his time over two years on Skype matters, focused on bringing in new management. He and Andreessen quietly changed out 29 of Skype’s 30 top managers. (In contrast, the recent firing of eight executives before the closing of the Microsoft (MSFT) deal — they’ll lose their chance at million-dollar payouts — caused quite a stir.) Thanks to its status as a venture-backed company with options to grant, Skype was able to double its engineering ranks and open a Skype facility in Silicon Valley.

The new team furiously started spitting out added features and new versions of Skype every four to six weeks, and dove into significant new businesses, including smartphone apps, deals to embed Skype in consumer products like TVs and game consoles, and partnerships with Facebook and Verizon Wireless (VZ). “The Facebook partnership was critical,” Durban says. “And the partnerships with carriers — they had thought of us as an enemy. Getting Verizon signed up signaled that one of the world’s largest carriers was not at war with us but was supportive.”

In fact, Skype was suddenly surfing tectonic shifts in communications. The wave of iPhones and iPads and Androids in 2009 and 2010 pushed wireless carriers to the realization that their most profitable business would be providing data services, not voice calls, and they came to see apps such as Skype as assets that would help drive sales of smartphones and pricey data plans.

By the fall of 2010, just a year after the buyout, Skype was surging: Users had climbed to 600 million from about 400 million a year earlier — and it saw rising usage of its video calling services. But it needed a CEO who could take the company public. (Josh Silverman, who was the CEO of Skype when it was a unit of eBay, had stayed on.) Durban contacted Tony Bates, a senior executive at Cisco (CSCO). They talked for nearly three hours — on Skype, naturally.

The clincher was Bates’s meeting with Andreessen. “I’d always been a big admirer but had never met him,” Bates says. “Going into the Andreessen-Horowitz office was an experience. They have this wonderful library in the lobby, and I looked for a couple of books that were special to me. One was Neuromancer, by William Gibson. I couldn’t find it, so that became a good opening to the conversation.”

Bates, a Brit with a deep technical background and big-company chops, was perhaps one of the few executives — “a needle in a haystack,” Durban calls him — who could wrangle strong-willed engineers spread across half the globe. He joined in October 2010, and Skype postponed its IPO, which gave Bates time to get the company into better shape.

Little did the executives know the delay would work in their favor: By early 2011, Skype was developing new ways to make money, including selling advertisers airtime during Skype video calls. Executives started talking up the video business — and a forthcoming IPO. Peter Klein, Microsoft’s chief financial officer, had been hearing the chatter and reached out to Durban in April. Microsoft, which had been looking for ways to bolster its fledgling efforts in mobile-phone software, saw Skype as a potential partner for voice and video calls; it also saw the software as an interesting way to enhance its broadband-connected Xbox gaming platform.

Durban, who jokingly likens the deal to marrying off one of his daughters, and Andreessen are uncharacteristically mum when it comes to the juicy details of the negotiations, and Microsoft declined to make Klein available for the story, but clearly Microsoft was bidding not against another buyer but against the valuation Skype expected to secure from its public offering. For Durban, Andreessen, and Bates, $8.5 billion in cash was an offer too good to refuse. So far U.S. antitrust officials have signed off on the deal, and European Union approval is pending.

So did Microsoft overpay for Skype, contributing to a new tech bubble? Spokesman Frank Shaw likens the deal to Microsoft’s $240 million investment for a 1.6% stake in Facebook in 2007 — now worth roughly $1.3 billion based on reports that put Facebook’s value at about $80 billion. “History doesn’t always repeat,” he says, “but there are similarities in terms of what people are saying about the Skype deal.”

Certainly Microsoft will be buying a fast-growing, well-positioned global asset with an unbeatable brand. But that’s what eBay thought when it bought Skype in 2005 for $2.6 billion. The devil is in how that asset is managed, and whether it can integrate with existing products and services. eBay blew it on both counts. If Microsoft does the same, we could wind up writing this story again with different names — or maybe some of the same ones — a few years from now.

–Kevin Maney is co-author of the upcoming book The Two-Second Advantage: How We Succeed by Anticipating the Future … Just Enough.

–This article is from the July 25, 2011 issue of Fortune.