(FORTUNE Magazine) – On a dreary day in early March, a few hundred aviation executives are in the midst of a very dull lunch. About halfway through it, Herb Kelleher steps into the room. Instantly the drab banquet hall in the Washington, D.C., Convention Center is buzzing. "He's here," the whispers sweep across the room. It's as if Leonardo DiCaprio has just walked into a room full of teenage girls. Okay, there's no screaming. But there are packs of industry honchos jumping out of their seats to run over and grab him, hug him--yes, even kiss him. Every neck in the room has turned, straining to follow him as he works his way to the front.

Kelleher is here today to deliver a speech on the sober topic of "The Future of Aviation." But his PR man warns me in advance: "I have no idea what he'll say--Herb usually just thinks something up minutes before he gets up there." Tanned, relaxed, and beaming at the crowd, Kelleher steps up to the podium. He begins somberly. "It is my practice to try to understand how valuable something is by trying to imagine myself without it. Following that practice has brought me to the clear, incontrovertible realization that..." Here Kelleher pauses. Looking around the room, he breaks into a broad grin and booms: "Wild Turkey whiskey and Philip Morris cigarettes are essential to the maintenance of human life!" The crowd erupts in cheers and whoops of laughter.

This is vintage Herb, the legendary CEO of Southwest Airlines, famed for wild partying, impersonating Elvis, riding a Harley. He once settled a business dispute by arm-wrestling over it rather than going to court. "Herb is crazy," one industry executive giggles when asked to describe him. "I was at an executive retreat with him once--he kept everyone up all night drinking and talking." On one occasion Bob Crandall, the formidable ex-CEO of American Airlines, made a snide remark about a Southwest promotion featuring SeaWorld's Shamu the Killer Whale. Soon afterward at a staff meeting, Crandall received--by special delivery from Kelleher--a massive bowl of chocolate pudding meant to look like whale poop. The card read, "With love, from Shamu."

But of course what makes Kelleher truly legendary is Southwest. Built from a scrap of an idea on a cocktail napkin in 1966, it is now, bar none, the best-run airline in the country. Since 1973 the company has not lost a dime. No other airline can make that claim. While other carriers have suffered multiple bankruptcies (Continental), crippling strikes (Northwest), and total failure (Pan Am, Eastern), Southwest has thrived. Its margins and balance sheet are the best in the business. Last year the company earned $474 million on $4.7 billion in sales. Its stock price is up 300% over the past five years, to a recent $20.

Now Kelleher is getting ready to pull off his biggest feat as CEO: letting go. Although he has said that he plans to "live forever or die in his chair," Kelleher, 69, and recently diagnosed with prostate cancer, is increasingly faced with the question What happens to Southwest after you're gone? Ever since news of his cancer hit last summer, Kelleher has been hounded by Wall Street and the press to tap Southwest's next CEO. EARTH TO HERB: PICK A CO-PILOT one headline ran. A recent Merrill Lynch report on the company cites succession as one of its main risk factors.

"The kind of contribution [Kelleher] can make to Southwest is to select the next leader and help that next leader make a successful transition," says Crandall, apparently bearing no ill will over the whale poop incident. Still, finding the next CEO of Southwest is not going to be easy. For a place like Southwest, which is so dependent on the character and personality of its chief, choosing the wrong guy would be disastrous. History is littered with companies that fell apart after celebrated chiefs departed. Look at Coca-Cola post-Roberto Goizueta. Or Toys "R" Us after Charles Lazarus. "If the board went out and hired a Frank Lorenzo [Continental's confrontational ex-CEO], there'd be a hanging or looting or something--it just wouldn't work," says Colleen Barrett, Southwest customer relations chief.

Kelleher knows it too. And for all his shenanigans, he is deadly serious about this issue. "The most important thing you should be thinking about is leaving something that lives far beyond yourself," he says. "I want to leave a legacy at Southwest."

On a bright late-March day in Dallas, Kelleher is sitting in his dingy, windowless office at Southwest headquarters. When asked why the CEO of a FORTUNE 500 company doesn't have windows, he replies, "The clear, unmistakable sign of a bureaucrat is somebody who worries about whether he has a window." Lighting up a Merit, he leans back into his deep green-leather chair and begins talking about cancer. Kelleher refuses to be rattled. "It's been on other people's minds much more than it's been on my mind," he insists. "I said to myself, 'Well, I have prostate cancer. I guess if I have a prostate, I have to do something about it. In the meantime I'm going to work every single minute that I can.' " In the course of his treatment Kelleher endured 42 radiation treatments. For two months he spent seven afternoons a week getting zapped with gamma rays. Once, while he was in the waiting room of the treatment center, a woman came over to him, held his hand, and soothingly said, "I bet you're scared." Kelleher replied, "Yes, I am. And you know what I'm afraid of? That I'll be bored to death! Forty-two trips for radiation treatments--not the most exciting thing to do." Laughing hard at the memory, Kelleher jumps out of his chair, cigarette ash falling to the floor as he moves. He's so animated and spry, it's hard to believe he's been sick at all. His doctors warned Kelleher that the grueling therapy would leave him too exhausted to work full-time. Yet to date he's never missed a day at work.

Kelleher's been at Southwest since the beginning. Thirty-four years ago he was practicing law in San Antonio when one of his clients, Rollin King (now a board member), came to him with an idea he'd cooked up in a bar. He wanted to start a cut-rate airline to fly between Dallas, San Antonio, and Houston. It took five years of legal wrangling--because of fierce opposition from now defunct competitors--but in 1971 the first Southwest flight got off the ground: Dallas to Houston for $20. At the time such cheap fares were revolutionary. Other airlines cost three times as much. To charge such fares and make money, the upstart airline was bent on slashing costs. That meant no frills and a fast turnaround--20 minutes in and out of the gate. Since then, Southwest's business model hasn't changed. Its planes have never served a meal and still take just 20 minutes to turn. As a result, Southwest's costs are 22% below the industry average. Its operating margins (16.5%) are triple the industry average.

Southwest's success has attracted many imitators--US Airways' Metrojet, Continental Lite, Shuttle at United, Delta Express. So far it's not clear that any of them has turned a profit, and one of them--Continental Lite--is out of business. How does Southwest succeed where others fail? "They have a huge competitive advantage," says Brian Harris, airline analyst at Salomon Smith Barney. "Their culture." Kelleher is more emphatic: "Our esprit de corps is the core of our success. That's most difficult for a competitor to imitate. They can [buy] all the physical things. The thing you can't buy is dedication, devotion, loyalty--feeling you are participating in a cause or a crusade."

Indeed, Kelleher's true gift as a leader is his ability to inspire his troops to be as passionate about Southwest as he is. "Herb makes you feel like you're part of a family," says Andrew Boniface, a stock clerk in Houston. It's a family that, like its patriarch, doesn't let ceremony stand in the way of efficiency--or fun. Pilots, for instance, will help load bags or clean cabins, if necessary, to stay on schedule. Gate agents sometimes restock planes. Flight attendants are famous for popping out of the overhead bins and telling jokes over the speakers. On Halloween employees throw raucous gate parties--complete with costumes, streamers, and cake. Not surprisingly, Southwest has the industry's fewest customer complaints, the fewest lost bags, and the most on-time arrivals.

Southwest's "esprit de corps" can be especially valuable in a crunch. In February, Kelleher sent a letter about the current fuel crisis to the home of every employee. Jet fuel, now $1 a gallon, costs three times what it did a year ago. Southwest uses 19 million gallons a week. "Our profitability is in jeopardy," he wrote. In a personal plea, he asked each worker to help out by saving $5 a day. That would, he explained, save Southwest $51 million annually. The response was immediate. One department offered to do its own janitorial work. A group of mechanics figured out how to heat the planes more cheaply. It's only been six weeks since the letter, but employees have already saved the company more than $2 million.

But as Southwest grows, sustaining zeal among the troops gets harder. Southwest already flies into 56 cities (up from 29 in 1989) and has 30,000 employees. Over the next five years it will spend $4 billion opening a dozen new destinations. "You have to make sure that they don't become little independent fiefdoms," Kelleher says. Recently tensions broke out between flight attendants and their schedulers (the ones with the sorry job of telling flight attendants they have to work on a day off). The flight attendants believed the schedulers were overworking them; the schedulers claimed the attendants were hostile and uncooperative. The solution was very, well, Southwest: Both sides had to switch jobs for a day and see how difficult the other side had it. For now, at least, the tactic has eased tensions.

To thrive without Kelleher's guidance, however, Southwest must be able to defend against infighting, fiefdoms, and other plagues of corporate expansion all by itself. Kelleher's job now is to teach Southwest to regenerate itself--its offbeat culture, its wacky traditions--even if he's not around. To make that happen he has created a blueprint, a sort of how-to, for being Southwest.

First off , Southwest is very careful about who it lets in the door. Only 4% of the 90,000 people a year who apply for jobs get in--you've got better odds at Harvard. Essentially, what Southwest is looking for are mini-Herbs. It actually uses a personality test to rate candidates (on a scale from one to five) on seven traits: cheerfulness, optimism, decision-making skills, team spirit, communication, self-confidence, and self-starter skills. Anything less than a three and you're a no-go. This goes for everyone--from pilots to mechanics. "We would rather go short and work overtime than hire one bad apple," says Libby Sartain, vice president of human resources.

Once hired, employees go through rigorous people-skills courses at the University for People, Southwest's training center in Dallas. In one recent class a group of new hires learned to read body language. One demonstrated "negative body language" by stomping past another, head down, hands folded across her chest. In another class a group of mechanics learned the art of positive reinforcement. "If one of your guys is having a bad day, instead of telling him what a bad job he's doing, maybe it's better to say, 'Hey, you've been doing a great job. Here are some ways you can do even better,' " offers one student, Steve Dosset. To protect Southwest's tradition out in the field, the company has set up "culture committees" at each airport it goes into. They are responsible for making sure the new site carries on the spirit of Southwest: the gate parties, the jokes, and the games. So far the committees appear to be paying off. At one recent gate party in Islip, N.Y.--1,600 miles from headquarters--Jeff Haag, a young customer service rep who's never met Kelleher or worked in Dallas, gushes, "This is what Southwest is about--our culture, it's huge!"

Still, to truly secure Kelleher's legacy, Southwest needs a successor. "Herb is going to be very hard to replace," sighs board member June Morris. "He's promised us he will live forever, and I'm going to hold him to it." The board insists no final decision has been made on the next CEO, but the likeliest candidates can be found in a team of managers who have worked with Kelleher a combined 119 years: customer relations chief Barrett, 55; operations chief Jim Wimberly, 47; corporate services chief John Denison, 55; general counsel Gary Kelly, 44; CFO Jim Parker, 53; and vice president for government affairs Ron Ricks, 50.

Of them, the most powerful is Barrett. She started out as Kelleher's secretary 33 years ago and still guards the door to his office. A small, white-haired, chain-smoking grandmother, Barrett is in many ways the muscle behind Southwest. When asked about what will happen to Southwest after Kelleher, she scoffs, "It's insulting to people like me--who have been here since day one--to have people think that the whole place is going to shut down [when] Herb is out the door." But Barrett says she's not interested in taking over. The rest of the team shies away from openly campaigning for the job. "Herb would be so disappointed in us if we were to play those games," says Ricks.

On this topic, Kelleher, for once, isn't talking. "You don't want to get people stirred up speculating two years down the line, 'What's going to happen to me when so-and-so comes in?' " he says. Still, he insists, Southwest's future is secure: "Just because you don't announce your plan doesn't mean you don't have one." When asked what type of person he sees as Southwest's next CEO, he replies, "We're looking for someone lucky. Like me."

FEEDBACK: kbrooker@fortunemail.com