(FORTUNE Magazine) – Lou Gerstner arrived at IBM on April Fool's Day in 1993 and found himself at a company that had become in many ways a sad joke. The colossus that once ruled technology had lost a record $5 billion in 1992. Top executives weren't focused on customers or held accountable for meeting financial and business targets. Gerstner's goal was simple: to change all that. And as he looked around at the mess he'd walked into, he found a kindred spirit: Sam Palmisano, who had recently been named to a top spot at IBM's services arm.

If there's a single reason Sam Palmisano will take over as CEO, assuming the top job on March 1, it's that he has so much in common with Lou Gerstner. The similarities are often overlooked, because in person the two men seem so different. Gerstner, 59, is gruff and often distant; Palmisano, 50, is personable--until crossed, when he lets you have it. But Palmisano was Gerstner's kind of guy even before Gerstner got to IBM. He thought nothing of flying off at a moment's notice to meet a customer halfway across the country. He held his reports to exacting financial targets. After a year or two of watching that kind of performance, Gerstner homed in on Palmisano, and the two would occasionally share cognac and cigars at the end of a long day.

There's another thing Palmisano and Gerstner have in common: As Palmisano assumes the top job, investors and critics are pounding the table, asking where the new CEO is going to find growth. That's long been the question, given that annual sales have increased an anemic 4% on average since 1994. But as Gerstner has shown, that question somewhat misses the point. He took a dispirited, directionless, money-losing collection of businesses and utterly transformed it. As Intel Chairman Andy Grove puts it, "He has done more than I ever imagined anyone could do with that company." The result is a giant that had profits of $7.7 billion last year--more than any tech company other than Microsoft--on sales of $86 billion, almost twice as much as any other tech company and enough to put it in the top ten of the FORTUNE 500. Sure, IBM needs growth, but for Palmisano, as for Gerstner, that issue is not necessarily the key. (As with every story FORTUNE has written about the company since 1997, IBM declined to comment.)

Gerstner did such an amazing job turning around IBM that his successor faces a very different set of challenges. Palmisano inherits an IBM near the top of its game, a company that is one of just a handful of healthy leaders of America's most important industry. So Palmisano's tasks are broader: How will he fare as IBM increasingly faces off against Microsoft? How can he lock in IBM's huge advantage in the enterprise market and steal even more share from the likes of Sun Microsystems, Oracle, and EMC? In short, how can he ensure that IBM delivers on the potential Gerstner revealed?

That Palmisano faces such questions is testimony to the Gerstner turnaround. In a way no one predicted, Gerstner harmonized IBM's complex mix of products and services. IBM's polyglot constituents include four major lines of computers, multiple types of software for each machine, a huge semiconductor operation, data storage, a big finance arm, miscellaneous products including printers, and a wide variety of services to help customers select, install, operate, and maintain computing systems. The problem Gerstner faced was that the commoditization ripping through the tech industry threatened the margins of all his hardware and software businesses. One way he addressed that was to play every financial card in his hand. This kind of aggressive bookkeeping has been widely criticized, but it did buttress the bottom line. (For a hard look at IBM's books, see "That Old Financial Magic" by Bethany McLean.) But Gerstner's most important move--which in retrospect seems like a stroke of genius--was to take IBM out of the commoditization game by emphasizing its services business.

The step was natural for Gerstner, who had been a bigtime purchaser of IT in previous jobs at R.J. Reynolds and American Express. He believed that if IBM could solve the IT problems of large corporations, it would win big sales, with recurring service revenues spread out over years and margins that were a lot better than those IBM could get by competing only at the product level.

To deliver on that strategy, Gerstner needed a focused, disciplined IBM--a far cry from the mess he inherited from John Akers. When he arrived, IBM managed by so-called foils. An executive pitching a project would come to a meeting and present his vision by displaying elaborate foils, or transparent slides, on an overhead projector. Thus were projects funded. Gerstner instead asked for written proposals in advance, then spent the meeting time interrogating his executives. On at least one occasion he walked into a conference room and ripped out the projector's power cord. And he kept the documents. If you said that investing $20 million could generate $60 million in new revenue within a year, you'd be back in his office a year later if those revenues didn't materialize. Says Frank Moss, who joined IBM in 1996 when he sold Big Blue his software company, Tivoli Systems: "It was Management 101, but Gerstner brought it to a company that was dysfunctional." Gerstner also upped the amount of executive compensation given as stock and options, set quotas for how many customer calls each executive had to make, and relentlessly pushed coordination among IBM's many divisions.

Thanks to all that work, today's IBM really delivers on Gerstner's strategy. When Global Services makes a big corporate sale, it does involve plenty of non-IBM products, including gear from rivals like Sun and Hewlett-Packard. But in the end, controlling the sale and design of the customer's system is to IBM's benefit. Says senior vice president Matt Thornton of Mellon Financial, whose e-commerce operation is a big customer: "They know that the traction comes from having enough--not all--of their stuff in the architecture, so that pulling IBM out is just too expensive. So now they recommend 60% IBM product, not 100% like before. But it's just as good for them, because you're still locked in." Paul Deninger, managing director of technology-specialist investment bank Broadview, echoes Thornton: "IBM's core competence is customer control."

IBM's shift to services has reshaped the industry. HP's plan to merge with Compaq, for example, is driven by the desire to assemble a comparable array of products and services. Says Compaq CEO Mike Capellas: "IBM's is the strategy we emulate." Adds Intel's Grove: "The key to IBM's success with its services business is that it wraps things around commodity products that differentiate them. Every other computer company has now adopted as its primary objective to be more IBM-like. It's kind of interesting that this service-driven strategy, an idea that everyone else is now copying, came from an outsider to this industry."

It's also interesting that IBM has weathered the technology downturn better than almost any rival. IBM's stock has been basically flat for two years. But consider what's happened to the competition. Of course troubled companies like Gateway (its stock is off 91% in two years), Compaq (down 55%), and HP (down 48%) are hard-hit. But look at the companies with technology or segment leadership: Cisco (down 64%), EMC (down 69%), Intel (down 29%), and Sun (down 73%). Some of these will rebound on the strength of their technology, while others will try to catch up by copying IBM. But the company Palmisano will run is unmatched in sales, services, and technology expertise.

While Gerstner was the first outsider ever to run IBM, Palmisano may be the ultimate insider. He's had more diverse IBM experience than any CEO before him, most of whom rose through the sales organization. Palmisano, too, worked in sales, but then began a tour that included IBM Japan, two stints at services, and jobs heading the PC and the mainframe business, among others. He served as executive assistant to Gerstner's hapless predecessor. He's an insider in a larger way too--he's a longtime friend and golfing companion of the Bush family, including both Presidents. His wife's family has vacationed for many years near the Bushes in Maine. Palmisano in 1996 purchased George and Barbara Bush's retreat in Kennebunkport.

And while Palmisano and Gerstner may have come to identical conclusions about running businesses, the two couldn't show more different faces to the world. Executives live in fear of Gerstner. But Palmisano's first instinct is to be kinder and gentler. Says a longtime executive: "Lou never makes you feel like you're part of his team. Sam--I loved being part of Sam's team. I loved the way he treated me." Yet he is no soft touch. Says Ira Hall, a senior deputy at Global Services until he left in 1998: "His is the discipline of profitability, cash flow, customer satisfaction, and no excuses." Says another longtime deputy: "Sam's got two sides--the superinformal side and the 'I'm going to tear you from limb to limb' side."

It will help Palmisano enormously that IBM is perfectly positioned for today's macro-trends in IT. Years of crazy-quilt spending on Web-related projects have left every big company with many unconnected and often poorly performing software applications and systems. Meanwhile the recession has CEOs hunkering down and resisting new projects. Most big companies are struggling to reduce the number of IT suppliers they deal with. "Customers want fewer providers, but they want a broader range of services," says Julie Giera, a services industry analyst at Giga Group. "They want one throat to choke if something goes wrong." Adds Broadview's Deninger: "Companies are saying, 'Don't sell me any new stuff. Make the stuff you already sold me work!' Who is better positioned than IBM to deliver that?"

Once, proprietary hardware was the glue that bound IBM to its customers. Now IBM's experts are its best asset. They can help customers figure out and implement the unique technology setups that allow them to differentiate themselves from competitors. Good IT staffers are hard to find, but IBM Global Services alone has 150,000. That makes IBM by far the world's largest IT services provider, even as services plays a larger and larger role in the industry.

To keep IBM ahead, Palmisano will have to develop new areas of growth. A key trend is likely to be the delivery of many sorts of software as a service, something like a utility. Computing power may increasingly be sold by the unit and delivered via the Internet. That may win new customers, given that they will pay only for what they use. The company also stands to expand in conventional outsourcing--already a $14-billion-a-year business in which IBM owns and manages data centers and even entire customer-service operations for companies like Fiat and Nextel.

Even as it hawks the services of its experts, IBM is engineering computers to manage themselves, cutting the amount of human intervention they need. That could boost demand by reducing the labor cost in customers' installations. Research chief Paul Horn has declared it IBM's "grand challenge"--arguably the closest thing to a vision to emerge under Gerstner. Horn calls his approach autonomic computing because the machines would regulate themselves much as the body's autonomic nervous system controls temperature and heart rate. For instance, when a new server is plugged into an autonomic network, the network might identify it, feed it the appropriate software and data, and load it with tasks, all without programmers' help.

If Horn's quest succeeds, it would be a milestone for IBM's vaunted R&D program, which for decades has failed to translate breakthroughs into products. IBM physicists, for instance, are unequaled at squeezing data onto disks--they set a world record in 1993 by increasing storage density to 354 million bits per square inch; last year they set the new record, 35 billion bits. Yet IBM's disk-drive business is struggling. Throughout the Gerstner years IBM has been the world leader in new patents; it earns well over $1 billion a year licensing those patents. Yet all that seems less impressive when you consider that in storage, networking, databases, and Unix servers, IBM has been eclipsed--during Gerstner's tenure--by EMC, Cisco, Oracle, and Sun.

For the moment IBM's success doesn't depend on commercializing new technologies. The company is sitting pretty as long as conservatism prevails among recession-stricken corporate IT shops. But when the economy rebounds, customers will again be hungry for innovation. Says Tom Bittman, top IBM analyst at Gartner Inc.: "It's time to focus more on real vision--to start placing bets." Predicts Deninger of Broadview: "There will be a market that emerges in the next two to five years that will deliver $20 billion in annual revenues before the decade is over. IBM needs to play in that market. But it's not clear now what it will be."

The likeliest place to look for serious market growth, though, is a sector that doesn't exactly play to IBM's strength. Big Blue is geared to big customers: Giga Group calculates that this year, for instance, the largest 5% of corporate customers will purchase 50% of IBM's mainframes. Yet the fastest growth in IT is in medium-sized and small businesses. Says Giga's Viera: "IBM doesn't have a mid-market strategy in services. They don't service small and midsized companies. Their size and their cost structure prevent it."

Which brings us to Microsoft. Small and medium-sized businesses are Microsoft country; selling to them is a top priority for CEO Steve Ballmer, who has recently rejiggered the company's services group in part to better reach those customers. And of course when you combine Microsoft with the increasingly powerful computers made possible by Intel's ever more powerful chips, you have the force of commoditization staring you right in the face. There's no way Palmisano can avoid the collision. Indeed, Tom Bittman of Gartner has no doubt that Microsoft is becoming IBM's No. 1 competitor. Sure, Palmisano's folksy demeanor may help win small-business accounts, just as Gerstner's no-nonsense attitude charmed the FORTUNE 500. But he'll need a new formula to make such sales pay.

He'll need even more than that. Winning new sales, executing Gerstner's strategy, and developing modest new markets will be enough for Palmisano to succeed only if everything goes right. As we know from the past couple of years, things always go wrong in the technology business. To shield IBM from that kind of headache, Palmisano will have to deliver something big, something we can't yet envision. He can't be just a caretaker of Lou's legacy. He has to surprise us as much as Lou did.

ADDITIONAL REPORTING: Suzanne Koudsi, Adam Lashinsky, Peter Lewis, Carol J. Loomis, Brent Schlender, Julie Schlosser, Fred Vogelstein, Noshua Watson

FEEDBACK: dkirkpatrick@fortunemail.com