(FORTUNE Magazine) – AT 12:30 ON A RECENT TUESDAY AFTERNOON, GARY KELLY, Southwest Airlines' new CEO, dropped in at a small mechanics' lounge in the bowels of Chicago's Midway airport. Nobody recognized him, so he introduced himself, shook hands, and said to several of the men, "Thanks for doing what you do." He was almost out the door when a mechanic in blue overalls took him aside and led him to a computer in the corner next to a ratty couch. The browser displayed a Yahoo Finance page with Southwest's ticker symbol, LUV. "What's happening here?" the mechanic asked Kelly. "That's my retirement, and it's not moving."

It was a fair question. For most of its 34 years in business, Southwest has been a company based on a bargain: Its mechanics, pilots, and flight attendants would out-hustle competitors, their enthusiasm conferring a competitive edge in a commodified industry. In return, the CEO would keep them secure--Southwest has never laid off an employee--and find ways to make the airline profitable while others lost their way and failed. The arrangement worked so well that Southwest developed a huge and devoted following--not just employees and frequent flyers but investors as well, who have rewarded it with an $11 billion market cap that almost triples all the other major airlines' combined.

It was quite a trick, and much of it was unreproducible; longtime CEO and co-founder Herb Kelleher, now chairman, is certainly one of the most charismatic people ever to have run a FORTUNE 500 company. But Southwest's success had prosaic ingredients, too: operational simplicity (only one type of aircraft), a Wal-Martian devotion to keeping expenses low to save folks money, and an emphasis on efficiency (no idle planes at hub airports waiting for connecting flights). Now every airline wants to play that game, and some are actually succeeding. The established "legacy" carriers are slashing costs, mostly wages and pensions. Upstarts like JetBlue and AirTran have copied Southwest's model and added amenities.

"Hey, I can admit it, our competitors are getting better," says Kelly, 50, the second CEO since Kelleher stepped down in 2001. "Sure, we have an enormous cost advantage. Sure, we're the most efficient. The problem is, I just don't see how that can be indefinitely sustained without some sacrifice."

So where does that leave Southwest? Not where you would expect. In the past year it has been doing things that previously would have been considered heresy: It now serves congested hub airports, links with rivals through code-sharing, and even hunts the big boys on their own turf. There is opportunity in this but also danger. "Slowly, Southwest is becoming what its competitors used to be," says Steven Casley of Back Aviation Solutions, an industry consulting firm. "The question is, how long can their unique culture stay intact?"

SOUTHWEST IS STILL, BY ALMOST ANY measure, the healthiest airline in the business--although that's like saying it's the least crippled patient in the ward. Along with the rest of the industry, it is still recovering from the effects of 9/11. Last year it earned $313 million--half what it did in 2000. Southwest's shares are down more than 30% from 2001 and have been hovering around $15 for the past three years. The stock is flat even though Southwest has hedged fuel costs better than anyone else in the industry--it pays $26 per barrel of crude oil for 85% of its needs, while the industry average is upwards of $50. If it hadn't engineered that cost advantage, it would have lost money in four of the past nine quarters.

But scan the many dials in the cockpit of this company, and you'll see small signs of trouble. The wages of its unionized workers, already more than 40% of operating expenses, are drifting higher and higher. Southwest pays its pilots an average of $170,000 a year, according to Airline Forecasts LLC, a consulting firm--31% more than United Air Lines pays after that carrier's deep cuts. Kelly's predecessor as CEO, Jim Parker, tried to negotiate a moderate salary increase with the flight attendants' union. When the talks grew bitter, Kelleher took over and negotiated a juicy 31% pay raise for its current contract. Parker soon resigned.

Kelly, who became CEO in July, argues that Southwest can continue to be the low-cost producer. He notes that the number of employees per airplane dropped to 74 last year from 89 in 2002, a cut that was accomplished through attrition, a soft hiring freeze, and generous severance packages. Kelly says that "hundreds of millions in savings" can still be found in efficiency improvements, although he's vague on specifics.

But Southwest's efficiency record has been so good for so long that it has less room to improve on nonlabor costs than some competitors: Travel agents' commissions, for example, have been at zero for some time. And 65% of Southwest customers already buy their tickets online. Kelly concedes that the airline "may have to seek revenue offsets." These, he says, could include "modest fare increases" as well as "more conservative labor contracts."

While Southwest's cockpit gauges are showing reasons for concern, it's the view outside the windshield that's really troublesome: Both the upstart airlines flying below it and the legacy carriers cruising above are encroaching on its airspace. Let's start with the smaller carriers. Historically they have never been much of a problem. There have been dozens of new carriers since the industry was deregulated in 1978. How many can you remember? Exactly. With few exceptions, they went bust--mostly by failing to emulate the Southwest model. Some expanded too quickly, others bought too many different airplanes, and one--ValuJet--had a fatal crash.

But in recent years upstarts have finally figured it out--borrowing the best of Southwest's thinking and some even adding value. The classic example is media darling JetBlue. It took the Southwest one-aircraft model and applied it on the transcontinental routes--adding small creature comforts like individual televisions, leather seats, and flashy snacks to snag business travelers from the big boys. And because it's new as well as substantially smaller than Southwest, JetBlue's costs are the lowest in the industry. AirTran, the reincarnation of ValuJet, has had remarkable success in the past few years, particularly by attacking Delta's Atlanta stronghold.

The legacy carriers, meanwhile, have been driving down their costs ruthlessly, some of them using the bankruptcy courts to force steep union concessions. They aren't close to parity with Southwest, but they are making progress. In the past year the big airlines have narrowed their cost disadvantage to 31% from 42%; they now fly seats for an average of 8.4 cents a mile, compared with Southwest's 6.3 cents, excluding fuel costs. The cost gap could narrow to as little as 20% next year, figures J.P. Morgan analyst Jamie Baker, if United, US Airways, and Delta get the additional $3 billion they are seeking in wage and benefit cuts.

In fact, if it weren't for record oil prices, some of the legacy carriers would be doing quite well this year. Take American Airlines. Its parent, AMR Corp., had a loss of $162 million in the first quarter. Yet had it paid the same price for jet fuel that it paid a year earlier, AMR would have earned a profit of $184 million. American has persuaded its union employees to work more efficiently, including longer hours at lower pay rates. It has smoothed schedules at hubs to boost efficiency. And by simplifying its fare structure and capping business fares, it is slowly winning back travelers from discounters.

If in the next five to ten years the major airlines can get their costs low enough while still providing things like international connections and service to big urban airports, what will be the point of flying Southwest?

KELLY HAS BEEN AT THE COMPANY for nearly two decades, first as a controller and then as chief financial officer, but he can't escape the shadow of Herb Kelleher --he's Al Gore to Kelleher's Bill Clinton. Even eight months into the job, he has barely redecorated Herb's former office in the airline's windowless Dallas headquarters. There's still a bobble-headed doll of Kelleher, flanked by giant photographs of Herb's heroes, Winston Churchill and Franklin D. Roosevelt. "I sort of stole his artwork," Kelly says, reclining in his armchair.

A 6-foot-3 accountant with perfect posture, Kelly has tried to borrow some of Kelleher's gonzo management style. At an office Halloween party last year he dressed up as Gene Simmons, the lead singer of the metal band Kiss, but it wasn't his cup of tea. At this year's party, he says, "I may just be Gary. It fits me better."

And it may fit Southwest. In response to the new competitive pressures, the company is becoming more ... we would never say conventional, for fear of having a drink thrown in our face, but at least more like the major airlines that it is accustomed to mock. To compete against them, it has to grow. That's because growth lets Southwest average in new, lower-paid employees and spread its costs over more seats. The airline expects to increase its capacity this year by at least 10%, adding 29 planes to its fleet of 417 Boeing 737s.

Expansion, though, is taking Southwest to some places it vowed it would never go. The airline used to avoid complicating its model with things like code-sharing and connecting flights. But last December, as AirTran was eyeing a move into Chicago, Southwest stunned the industry by buying a share in bankrupt ATA and linking up with it in a code-sharing agreement at Midway airport. Southwest also bought six more gates for itself there, bringing its total to 25 of the airport's 43. Soon it will control 16% of the Chicago market. While that is well behind United and American, Southwest may close that gap by the end of the year. Southwest's customers can now easily connect through ATA to such cities as Boston, Denver, Minneapolis, and Honolulu; some would argue that Southwest is creating a hub.

Southwest also used to avoid competing with the majors on their own turf, preferring to nip at their heels from smaller regional airports. But last year it started flying to Philadelphia, and this month it will add service to Pittsburgh; both cities are major hubs for US Airways. Southwest is even rumored to be after Charlotte, N.C., US Airways' last stronghold.

It's no accident. US Airways, in bankruptcy since 2002, is the airline considered most likely to liquidate. If that happens, Southwest will be in position to take over a substantial portion of the northeast corridor. In April, though, US Airways and America West announced that they were discussing a possible merger. If it succeeds, Southwest will be drawn ever deeper into fare wars with a potentially stronger US Airways--just the kind of battle it used to leave to others.

No one in senior management at Southwest will concede that the airline is becoming a different creature, of course--this is a company with a big psychic investment in being the underdog. "We're bigger, let's put it that way," Kelleher says. "I think the airline business is fundamentally an opportunistic business.... We suddenly have some opportunities materializing that are new to us." The question, of course, is whether Southwest can continue to play its own game as it goes on the offensive.

WITH CUSTOMERS MIGRATING TO THE web to buy tickets, Southwest last year decided to cut costs by closing reservations centers in Dallas, Little Rock, and Salt Lake City. But it didn't fire a single employee. In fact, the company picked up the cost of relocating them or paid for them to commute by air to jobs in other cities. It's a far cry from the way a lot of other airlines behaved last year--cutting wages up to 30% and defaulting on promised benefits. "We don't do those kind of things," says Colleen Barrett, the company's president. "That's what our competitors do. At Southwest, our employees come first."

This is not a fuzzy matter of morale--Southwest's culture has been its competitive advantage. You can't put it on a balance sheet, but it's something close to priceless--those perky flight attendants are all that keep a no-assigned-seating policy from turning into a stampede. That leaves Kelly walking a fine line. In private he admits he can't rule out salary cuts--something that in public he tends to gloss over.

In February he addressed employees at the company's Message to the Field conventions, held in five cities each year. The one just outside Dallas, at the enormous Nokia Theater, was a typical Southwest blowout. Families tailgated. People held up homemade signs reading I LUV SWA, HOUSTON MECHANICS LUV GARY, and GARY, WE'VE GOT YOUR BACK. There was a contest for the loudest employee group (the flight attendants have won for as long as anyone can remember). And when Kelly walked downstage, thousands of people jumped to their feet and cheered.

Kelly gave a 15-minute speech, recapping the airline's financial performance and its plan for the rest of the year. Toward the end he told the crowd, "The Southwest brand is under attack. These next years are going to be some of the hardest the airline has ever had. Be prepared for some sacrifices." The crowd fell still. In the silence, a woman wearing a bright-blue T-shirt with I'M SWA on the back leaned toward the man next to her and whispered: "I'm going to need a drink after that speech."

FORTUNE.COM SUBSCRIBERS ONLY

Read more online, including "Southwest Finds Trouble in the Air."

FEEDBACK bgimbel@fortunemail.com