If you want to find the new jet set, head to Sepang, Malaysia, before sunrise, to a building that looks like a beige Ikea. The Low Cost Carrier Terminal at Kuala Lumpur International Airport has no frequent-flier lounge, no sit-down restaurant, no moving walkways. It’s basically a hangar for people, thousands of them, who throng the place every morning to catch a flight on the terminal’s dominant carrier, AirAsia.

At 7:30 a.m., a fat, rumpled figure in black slacks and a white shirt saunters through the glass doors, escorted by a blast of humid air. Eyes fixed on his phone, he doesn’t look up except to glance at a departures board that lists one tongue-tripping destination after another: Langkawi, Jakarta, Kuala Terengganu. But at the sight of his round face and red cap—it reads “AirAsia: Now Everyone Can Fly!”—travelers nudge each other. One woman whispers to another, “He is the big boss.”

The big boss is Tony Fernandes, a former music executive who, just seven years ago, had no airline experience. Today, he runs AirAsia, which he bought out of near bankruptcy for 25 cents and a pile of debt in 2001 and turned into one of the world’s fastest-growing airlines. Under Fernandes’ watch, AirAsia has never posted a quarter in the red. For the 2007 fiscal year, it reported a pretax profit of $79 million—more than triple that of 2006—on revenue of $458 million, a 17 percent margin that is third best in the industry, behind Brazil’s Gol and Ireland’s Ryanair. About 18 million passengers are projected to fly AirAsia next year. Ryanair, the world’s biggest low-cost carrier, from which AirAsia has borrowed much of its business model, took three times as long to hit the 18-million-passenger mark.

AirAsia is also the most prominent example of the broader revolution taking place in air travel. As full-service carriers in North America and Europe invest in pricey frills like flatbed seats to squeeze more money out of premium passengers, dozens of low-cost carriers in the developing world are taking a more radical—and profitable—­approach.

These airlines are democratizing air travel by offering extremely cheap fares. Gol has sold tickets from Rio de Janeiro to São Paulo for $20; Air Arabia advertises fares of $44 between its hub in Sharjah, United Arab Emirates, and Bahrain; AirAsia prices some seats on flights within Malaysia at $3.

Fernandes now plans to go further. This fall, AirAsia will start service from Kuala Lumpur to the Gold Coast, a region in Queensland, Australia. It hopes to add London next year, eventually expanding to U.S. destinations. Virgin Group founder Richard Branson is a believer; in August, his company bought a 20 percent stake in Fernandes’ long-haul operation, AirAsia X (which is set up under a separate corporate structure), for about $7 million. Still, the move is a big gamble, and history is not on Fernandes’ side. Many upstart airlines—from People Express to ValuJet—have run into problems during ambitious expansions. But Fernandes remains undaunted. “We’re going to be the largest carrier in Asia,” he says, “maybe even the world.”