Southwest Airlines’ CEO Gary C. Kelly Sets the Carrier’s New Course

Can a mild-mannered bean counter take a carrier co-founded by wild man Herb Kelleher to the next level of greatness? Gary C. Kelly and Southwest Airlines are banking on it.

It’s not true, you know. the cocktail napkin thing. the triangle connecting San Antonio, Dallas, and Houston. The business plan that started Southwest Airlines. False. A lie.

Executive Gary C. Kelly wants Southwest Airlines to leverage its brand in new ways. photo courtesy of Southwest Airlines

Well, maybe not a lie. Maybe more of a legend. A myth, perhaps. A myth that Southwest Airlines is happy to sustain. They tell it something like this: Back in the days of yore, San Antonio businessman Rollin King met attorney Herb Kelleher at San Antonio’s swanky St. Anthony Club. After some—perhaps many—magical libations were consumed, King suddenly grabbed a napkin and sketched out an idea for a low-cost airline with point-to-point service between three Texas cities. Ding!

Rollin King, though, says he never did any such thing. “No, that’s not true,” King told me one morning over breakfast at The Mansion. (Months later he repeated this denial to The Dallas Morning News.) Southwest, to be fair, usually recounts the mythical cocktail napkin with the coy disclaimer, “As company legend goes … .” Still, the story lives on. It’s even taught today in business schools as an un-disclaimed truth. Company myths are like that. They endure better than Norse ones, possibly because Odin, despite being an all-powerful, one-eyed god, did not have a marketing department.

But therein lies a problem for Gary C. Kelly, the current chief executive officer of Southwest Airlines. The fabled days of Southwest’s founding, its early struggles, and its eventual, stunning successes, live on. People know about the days of yore—people who work for Southwest, who fly the airplanes, who invest in the company, and who advise others whether (or not) to invest. And a lot of those people judge today’s Southwest Airlines by yesterday’s milestones.

Milestone math …

›› Southwest plans to grow next year by about 6 percent. Six percent? What happened to 30?

›› Southwest set up service last year at Washington’s Dulles International Airport with two gates and a dozen flights a day. Two and a dozen? What happened to the blitzkrieg strategy of entering an airport and saturating it with numerous flights departing every half-hour?

›› Southwest earlier this year told a passenger to get off the plane because her skirt was several inches too short. Several inches? What happened to the easy-going airline of hot-pantsed flight attendants, the LUV airline?

All that math and all that old mythology adds up to make Gary Kelly’s job as Southwest’s current CEO arguably the hardest in the airline industry. Where other airline executives can be deemed successes if they simply stave off bankruptcy, Kelly has to do more than just maintain profits and grow the company. Sure, he’s managed to do both those things in his three-year tenure as CEO, despite stiffer competition, soaring oil prices, and an industry that has only now righted itself from a desperate tailspin. But when some people are expecting crazy cocktail napkin business plans and/or magic hammers spewing thunder and lightning, is that enough? Well, that depends on how you measure the man against the myths.

THE MYTHOLOGY: Southwest Airlines has a highly motivated work force that’s led by a charismatic, maverick executive.

Herb Kelleher kisses co-workers. On the mouth. He smokes. He drinks. He tells the most illustrative stories of any Fortune 500 executive. He tells dirty jokes (without asking writers like me to keep them off the record, thankfully). He laughs like a crazy person. He’s nuts. Hah! Get it? Nuts. Like the peanuts that Southwest became famous for serving before every kid in America became allergic to peanuts. Woo!

Kelleher is not really nuts, of course. But he is different. Singular. A business maverick. And, though he is set to officially step down from Southwest’s board next year, Kelleher has been, for decades now, the personification of Southwest Airlines—the down-to-earth, happy-go-lucky, yet totally driven boss of the on-time, everyman’s airline. And Gary Kelly? Well, have you ever heard anyone called a “maverick accountant”? Probably not. Kelly is an accountant—or, at least, that’s what he was before he joined Southwest Airlines in 1986, at age 31. But he’s no maverick. And, frankly, he doesn’t want to be.

“I am very comfortable with who I am and what my capabilities are,” Kelly says from Herb’s old, windowless office in Southwest’s headquarters at Dallas Love Field. “There’s only one Herb, and Southwest is fortunate to have him as our co-founder, as our CEO for 20 years, and as our chairman today. We’ve got our legend, and I don’t aspire to be a legend. But, and Herb will tell you this, it was never all about Herb and it’s certainly not all about me. I actually think that I’m a good fit for Southwest Airlines right now. So I try not to worry about comparisons. But, I try not to worry about anything, to be honest.”

Believe that. Kelly is a one of those particular breeds of Texas native—relaxed, confident, pleasant, and soft-spoken with one of those lightly twangy accents. You could easily imagine him catching passes in one of those Brett Favre Wranglers commercials. Or throwing them. Kelly, who stands 6-foot-3, was the team captain and quarterback of his high school team in his native San Antonio. In fact, his football career actually begat his first experience with Southwest Airlines. In 1972, when the airline was just a year old, flying that legendary triangle between San Antonio, Dallas, and Houston, Kelly took his very first trip on a plane. He flew Southwest from San Antonio to Houston to visit Rice University, which was recruiting him for their football team. As he recalls, it was a Saturday morning flight, “and I think there were two other people on the plane besides me. So, I thought, this company isn’t going to be around very long.”

That also sounds like a myth. But Kelly doesn’t strike you as a fibber. He’s too bookkeeper-ish for that. In a good way. Where Kelleher talks in corporate parables—insightful anecdotes flow out of him, appropriately, like bourbon pouring from a cask—Kelly speaks almost exclusively in broad strokes, with lots of data thrown in. He’s a matter-of-fact type who chooses his words carefully. So you believe him when he says he believes he owes Kelleher a chance to retire. (Kelleher will, technically, still be employed by the company, working as needed as sort of a corporate memory bank—or perhaps at the Southwest kissing booth.) You also believe Kelly when he shares credit with Kelleher and Southwest’s president Colleen Barrett for setting the company on its current course. (In turn, they spoke highly to me of Kelly’s leadership abilities—specifically praising his ability to connect with Southwest employees.)

You believe him because Kelly is not afraid to tell you that some of the things that made Southwest what it was—the hot pants, the wacky TV ads starring Herb dressed up as a referee, the booze giveaways intended to lure new passengers—are now only history. “We have to be very blunt and acknowledge that things aren’t the same here,” Kelly says. “We don’t dress the same as we did in 1971 when the company was founded, and none of us are the same age as we were then. It is a significantly different world that we live in and it is also a dramatically different airline industry. The only comparison between today and 1971 is our people. We’ve always valued our people. We’ve always had a very special culture. The fact that we’ve been able to maintain this unique personality and culture and our efficiency and proficiency—we’re still renowned as one of the great airline operators in terms of reliability and safety—from when we had three airplanes to now when we have 520 airplanes, I think, is truly remarkable.”

THE MYTHOLOGY: Southwest Airlines is an underdog upstart fighting the entrenched industry powers.

An underdog Southwest Airlines is not. With right around 520 planes (and counting), Southwest has the second-largest fleet in the industry. It offers more daily departures—some 3,300—than any other airline in the world. And it carries more passengers every year than any other airline. At many of the airports it serves—Baltimore/Washington’s BWI, Las Vegas’ McCarran International, and Chicago Midway among them—Southwest is the dominant carrier. The company will earn more than $9 billion this year. And it employs some 34,000 people across the country. Put another way, Southwest Airlines today is the entrenched power.

Gary Kelly deserves more than just a small share of the credit for that.

Kelly reached the CEO’s post in July 2004 after a slow, steady, accidental, and unexpected climb to the top. Three years after being hired as controller in 1986, Kelly was named chief financial officer. The promotion was in part a result of Kelly leading a technological overhaul at Southwest. Maybe you’re old enough to remember that the airline used to issue paper receipts from cash registers. On the back, the receipts read, “This Is A Ticket,” so passengers would know the receipt was also their boarding pass. Kelly—whose pre-Southwest background was both in accounting and in software development—helped change that.

He made his real mark, though, in 1999 as part of the team that developed Southwest’s fuel-hedging program. Southwest used its deep cash reserves to buy options protecting it against future fuel price spikes. When oil prices soared and travel sunk after Sept. 11, 2001, those hedges were the key to keeping Southwest in the black. Southwest was the only major airline that didn’t lose money in the year after the terrorist attacks.

Only months before, in June 2001, Kelleher stepped down as CEO after 20 years in the post. He stayed on as chairman, promoting longtime Southwest executive Jim Parker to the CEO position, naming Barrett chief operating officer, and elevating Kelly to executive vice president.

Though the airline stayed profitable, Parker’s tenure was turbulent, marked by the most pronounced labor strife in Southwest’s history. In July 2004, Parker suggested he should step down, and Kelleher and the board voted Kelly to succeed him, even before consulting Kelly himself. The news came as something of a surprise, as you can imagine. “Becoming CEO wasn’t an aspiration that I had early on,” Kelly says. “But I enjoyed leadership as executive vice president, and when I moved to CEO I found that my background had me very well-prepared for my management duties. I guess everybody gets lucky once in a while.”

Still, Kelly’s good fortune was tempered by a looming problem. You know what happens to entrenched powers? They get, well, entrenched. Set in their ways. Stuck. And that’s what, in many ways, Southwest was in 2004. It was an airline that was very good at doing what it had always done, but not prepared for change.

And there seemed to be a clarion call for change as Southwest kept growing. Specifically, it appeared to most of the company’s executives and to many of the analysts that followed Southwest, that the company would have to end its “cattle call” boarding procedure in favor of the assigned seating practices of other major carriers. Trouble was, as Kelly recalls it, Southwest was totally unable to implement assigned seating or any other similar systemwide change.


>> Southwest is no longer an underdog, but a dominant carrier.

>> To better compete, CEO Gary Kelly shuffled top execsand enhanced communications.

>> The airline’s hallmark remains: Keep your people at the top of the pyramid.

Its vaunted, flat corporate hierarchy—where many important decisions didn’t go “up the chain,” but were handled by empowered, individual leaders—had one little operational flaw. Empowered leaders in different departments weren’t talking to each other enough. “I don’t think we weren’t communicating well because of a lack of desire,” Kelly says. “I just think people were busy.”

For instance, Southwest’s marketing department wanted to evaluate whether the airline should adopt assigned seating. But almost no other department was thinking along the same lines. “Other departments weren’t engaged,” Kelly says, “They had their own priorities. All of our departments were just not well-coordinated to undertake a massive change like assigned seating. And that really was the wake-up call for all of us.”

Who woulda thunk it? Southwest Airlines, that nimble, un-corporate place where people wear jeans in the executive suite, where gate agents are free to make decisions that, at other airlines, would require a vice president’s sign-off as long as it’s benefiting the customer—that Southwest Airlines—was unable to change? To quote Ralph Wiggum of The Simpsons TV show, “That’s un-possible.”

Kelly’s answer was Reorg 101—he switched up the executive team and opened new channels of communication between departments. The results of that change, one of the more dramatic top-level overhauls Southwest Airlines has seen in its 36-year history, are only now evident. Kelly insists the company is now built for speed, as the MBA kids like to say. “As much as anything, we’ve reorganized ourselves so that we all understand what the priorities are today,” Kelly says. “We’re all in sync with what our vision is for the future, and I think today we have, by far, the best management team in the company’s history.”

MYTHOLOGY: Like the cocktail napkin says: Southwest flies point-to-point. With one aircraft type. With frequent flights. With low fares. With open seating. No one else does it that way, and so that’s the way—the only way—Southwest makes money.

At a news conference this past October, Gary Kelly showed that he’s not entirely a number cruncher. In announcing Southwest’s long-anticipated decision on its boarding policies, Kelly cued up a recorded drumroll. Honestly, it was awkward. But it was a maverick’s move—not exactly the kind of thing you’d see Rupert Murdoch do during a press event, especially at a pivotal moment in his company’s history.

After the drumroll Kelly announced, “That’s right, I’ll say it. No more cattle call.” After almost a year of studying options and surveying customers, Southwest had decided to change its boarding procedures, all right. But it wasn’t going to offer assigned seats like every other big airline does today. That shocked some analysts, who had for years said Southwest needed assigned seats to expand into new markets—particularly into bigger airports like Dulles and San Francisco International Airport, where the so-called legacy carriers dominate.

So, there you go: Gary Kelly and Southwest Airlines are still stuck in their old ways, married to an outmoded model. Right? Actually, no. Kelly and many other top executives at Southwest actually assumed they would be adopting assigned seats. “One of the No. 1 complaints that our president, Colleen Barrett, had gotten for years from customers was about the lack of assigned seating,” Kelly says. “So, this notion that customers preferred that they have an assigned seat came through loud and clear to us. That was our presumption until 2006, when we did the research. And what our customers told us was, ‘No, we like choosing our seat, we just don’t like standing in the boarding line.’ I’m not saying there aren’t advocates of assigned seating, because there obviously are. But they are not the majority and are far from 100 percent.”

Actually, in Southwest’s research, it broke down like this: roughly 60 percent of customers wanted some form of open seating, with the remaining 40 percent preferring assigned seating. (Excusing some speculative math: That actually makes perfect sense. There are 137 seats on a Southwest Airlines Boeing 737-700. That’s roughly 92 coveted aisle and window seats and 45 dreaded middle seats — not exactly a 60-40 percentage split, but pretty close.) The bottom line was that Kelly had helped Southwest get ready and, at last, be able to change. Yet most of its customers didn’t want that change to come.

Perhaps that’s because, these days, Southwest isn’t the exception so much as the standard in air travel. “We’ve seen more competitors encroaching on our space,” Kelly says. “In the past, we enjoyed a very significant cost difference and low-fare brand differentiation vs. our airline competitors. But today there is an imperative in the industry to get costs down. There’s actually more competition today. Pile on top of that the fact that we are far and away at record energy prices—just in the last three years, crude oil has more than tripled. The impact of the energy cost changes on our cost structure is an increase of 20 to 30 percent. That means much higher competition, much higher energy costs, and much higher overall costs. We are adjusting to all of those things.”

Not well enough, according to some. Aviation consultant Michael Boyd of the Colorado-based Boyd Group, for one, told The Dallas Morning News in August that “Southwest has to modify its model because parts of it don’t work anymore.” At a Boyd Group conference in October, he added, “When they do, they’re going to be the nastiest competitor on this planet. … If you’re American or any other carrier, watch out for Southwest.”

In a report for the Prudential Equity Group this spring, stock analyst Bob McAdoo suggested that Southwest is bleeding money on a plethora of new routes, but seems unwilling to do anything to change that. He says 83 percent of the new routes that Southwest has launched since 2003 are unprofitable today.

When I ask Kelly about that, he shrugs. Well, verbally at least. “Our new markets have performed exceptionally well for new markets,” he says. “But the profits in our new markets are under pressure just like the profits in our mature markets. So I don’t accept the analyst report that you’re referring to. It was criticizing our new-market development entirely. The fact of the matter is that our overall profitability is not where we want it to be. We know that and we’re obviously taking steps to address that.” Said another way: No one at Southwest will deny that several of its new markets are money-losers. But they’ll also tell you that’s nothing new—that new markets take time to develop. That’s why Southwest offers cut-rate fares initially—to get the market addicted to its brand of service. It’s worth noting that JetBlue and Virgin America have embarked on the same strategy. Indeed, Virgin has stuffed its bank account with cash that it’s prepared to lose in the hopes of building a following through low fares and stylish service.

With that kind of competitive pressure, what’s the newly entrenched power to do? Add $1 billion to the bottom line in the next three years, is what. At least, that’s the plan. Forget the new routes: Kelly thinks Southwest can leverage its brand in other profitable ways. For one, directly selling vacation packages and rental cars on, which just happens to be one of the world’s most visited Web sites. For another, offering international destinations, through code-share partners like ATA Airlines, by 2009. And also by pushing its frequent-flier program harder, particularly to business travelers.

Still, therein lies the biggest management challenge for Gary Kelly. Southwest has to look for those alternative revenue sources now. The domestic airline industry might well be maturing right at a time when competitors are behaving more and more like Southwest, and at a time when oil prices are straining profitability. So even if those new markets McAdoo is critical of start paying off, even if that billion bucks does materialize on the bottom line, won’t Southwest Airlines circa 2007 pale in comparison to Southwest Airlines circa, oh, anywhere from 1971 to 2001? And if it does, how do you keep that go-go, happy-go-lucky, Herb-like work force going?

You do it the Gary Kelly way. Nice and easy. (Coincidentally, also the Frank Sinatra way.)

“I believe that whether you’re trying to play golf or throw darts or run an airline, you’ve just got to stay loose and you can’t get uptight about the various challenges,” Kelly says, sounding, well, pretty relaxed. “We’ve had very significant changes in the past decade. But are we profitable? Yes. Are we matching the growth we had in the 1990s? No. So we just can’t be satisfied with these results.”

And although the ways in which Kelly plans to push Southwest forward are myriad and more complicated than any spreadsheet he might have worked on back in his CFO days, as far as he’s concerned, keeping Southwest’s unmatched, un-possible streak of financial success going is nice and easy, too. Keep the people happy and the profits will come. “We’ve always been famous for keeping things simple and keeping our people at the top of our pyramid,” he says. “And we’re still true to that. We’re adjusting to high fuel prices or to more competition but we’re not losing our heart and soul—and that’s the people of Southwest Airlines.”

Gary C. Kelly, Southwest Airlines’ Team Captain

PERSONAL HISTORY: Born in 1955 in San Antonio. Married for 30 years to wife, Carol. Couple met in middle school at age 13. They have two daughters, Caroline and Elizabeth.

EDUCATION: BBA in accounting, University of Texas at Austin. Is also a CPA.

WORK HISTORY: Out of college, worked as an audit manager for Arthur Young & Co. in Dallas. Later hired as a controller by Systems Center Inc., a start-up software company that became part of Irving-based Sterling Software. Hired as controller for Southwest Airlines in 1986; promoted to chief financial officer in 1989, executive vice president in 2001, and CEO in 2004.

KEY WORK ACHIEVEMENTS: Helped lead the company’s first technology overhaul, an effort aimed at creating a modern system for issuing tickets and replacing Southwest’s cash registers, which dispensed receipts/boarding passes. Later, helped develop the airline’s fuel-hedging program, which was likely the biggest single factor keeping Southwest profitable after the Sept. 11, 2001, terrorist attacks and a subsequent run-up in oil prices.

KEY NON-WORK ACHIEVEMENT (ESPECIALLY IN TEXAS): In San Antonio, was quarterback and captain of Churchill High School’s football team in 1973. Earned a football scholarship to the University of Texas at El Paso, but later transferred to UT Austin to study accounting.

WANNA GET AWAY: Kelly and his wife still maintain a home in San Antonio and he often flies home for the weekends on a Southwest flight. He insists on sitting in the back of the aircraft to visit with the flight attendants or near the front to visit with the pilots.

HE FLIES TO WORK, TOO. SORT OF: Kelly, whose father worked as an accountant in a car dealership, drives a Porsche 911.

HE’S NOT HERB. BUT THEY SHARE TWO THINGS IN COMMON: Kelly and Southwest’s legendary co-founder Herb Kelleher were both born on March 12. Although Herb’s March 12 was in 1931. Both have also dressed up in an Elvis Presley jumpsuit for company functions. But that was just a one-time thing. “We have different styles,” Kelly insists. “He’s dressed up as Klinger, but I’ve dressed up as Gene Simmons.”


Keep me up to date on the latest happenings and all that D Magazine has to offer.