It was almost a regular day at work for Malaysia's most unconventional CEO. AirAsia's Tony Fernandes had just bid goodbye to a planeload of departing passengers and hello to the latest addition to his company - the 15th Boeing 737-300.

This is only to be the first of several such occasions this year. Come December, AirAsia is set to double its fleet and launch the year's biggest initial public offering (IPO) exercise to raise capital to a tune of some RM1 billion.

The man behind the success story was modest when describing his two-year-old company: "We are nobody. We are not particularly rich or connected."

But Fernandes' disclaimer belies the astonishing performance of a company whose growth has persistently outstripped even the most optimistic projections.

When AirAsia started its joint venture in Thailand in January, analysts expected the operation to turn profitable within a year. AirAsia made it to the black in the first month.

All this, and Fernandes' casual attire of jeans, T-shirt and a baseball cap when meeting with his 'guests' (as he calls his passengers), has made the 38-year-old CEO one of the most recognisable faces in the country.

"People are generally surprised, for a start, to see me in a T-shirt but secondly, just to be out there (meeting them)," he said in a recent interview.

"They used to recognise me only when I wore my red cap but now (they can) even without it."

On this occasion, Fernandes' T-shirt - a memento from his recent trip to Necker Island, the private Caribbean paradise of Virgin boss Richard Branson - was itself a hint of the direction that the airline could be taking.

A new deal?

Following the success of Virgin Blue in Australia, industry analysts have been closely watching Branson for similar overtures into the lucrative yet largely untapped Asia-Pacific market. One avenue for this has been said to be the possibility of Virgin buying a stake in AirAsia.

Fernandes would not confirm the speculation but added coyly, "Wait and see, wait and see. I won't rule it out. We are friends and we share a similar vision... Maybe."

AirAsia could do much worse than to welcome Virgin on board as a partner. In addition to co-opting a potential competitor, AirAsia could pick up a few more tricks from the experienced corporate maverick.

By his own admission, Fernandes - an accountant by training with no prior experience in the aviation industry - said he borrowed "a hell of a lot" from the tried and tested methods of European budget travel pioneers such as Virgin, Easyjet and Ryanair.

"My partner (Conor McCarthy) was from Ryanair. He was their chief operating officer. I think what we have done is taken a bit out of every low-cost carrier and put in our own Malaysian culture and the way we do things."

More importantly, AirAsia is going to need all the insight it can get on how to battle established national carriers such as Malaysia Airlines (MAS) and Singapore International Airlines (SIA) while staying one step ahead of copycat set-ups that are mushrooming across Southeast Asia.

On the home front, the airline was under attack only a couple of months ago by then Tourism, Arts and Culture Minister Abdul Kadir Sheikh Fadzir for allegedly misleading customers with its low fare advertisements.

Fernandes brushed aside the spat saying that the misunderstanding occurred only because of general unfamiliarity with the operating methods of no-frills airlines. At the promoted rates, he stressed, at least 20 to 30 percent seats would be made available.

These incidents aside, Fernandes was keen to highlight the support that he has received from the government.

"We are in business because of the government. Let's be very clear about that... The government was very protectionistic when we started out but hey, we were allowed to start and prosper. When MAS put up their super saver fares, the government stopped them from killing us," he revealed.

Fresh competition

A bigger challenge for Fernandes has been to find ways of tapping into the demand for low-cost travel in neighbouring Singapore.

His latest attempt to bridge the distance between Johor's Senai Airport and Singapore was thwarted when buses chartered by AirAsia to send passengers into Singapore were impounded on their first day of operation.

And operational hiccups would not be the only problems for Fernandes from that direction. By the end of the year, AirAsia will face competition from two new carriers based in the island republic.

ValuAir, a private start-up headed by former SIA managing director Lim Chin Beng, is planning to make its maiden flight in July while SIA budget spin-off, Tiger Airways, is expected to enter the foray by year-end.

Questioned about this, Fernandes was unfazed and even appeared to be looking forward to the battle ahead with some relish.

"I don't even know where the competition is. It's just talk at the moment. Nothing has taken off yet.(but) there is a lot of face involved and (SIA) will throw everything at it.

"Look at it this way. If Tiger is to operate budget flights from Singapore, who are they going to be in direct competition with?"

Thaksin link

While European low-cost carriers survived the early onslaught by deep-pocketed giants such as British Airways and Dutch national carrier KLM with the help of strictly enforced European Commission competition laws, Airasia does not have this luxury.

Fernandes' armour comes from an unexpected quarter. "It's the press. It's my only weapon against them," he said, underscoring the value of the positive image he has generated with the media.

This, he learned no doubt from the irrepressible Branson who is a popular figure with the press for his many publicity stunts.

Other than this, Fernandes attributed AirAsia's success thus far to the company's creativity in coming up with new ways to map uncharted territory.

For instance, he explained that the joint venture in Thailand had been necessary in order to obtain the rights to ply the kingdom's domestic routes.

"It is kind of ingenious," he mused. "It's the first time in the world that it has happened. Air France has now done it with KLM. No one really thought it could be done before."

Fernandes rejected with some vehemence the suggestion that the sweet deals Airasia worked out in Thailand were in any way related to the fact that his Thai partner, Shin Corp, is the family firm of Prime Minister Thaksin Shinawatra.

"We wanted to work with them because they were the best fit with us. If we have to choose again, we would still pick them because they are good," he said.

"The Thaksin (link) has been more of a nightmare because of what people keep saying. Thaksin will not even be in power forever. He might lose in an election."

New destinations

Meanwhile, Fernandes is propelling ahead where other countries are concerned. Starting next month, AirAsia will be expanding its wings to Indonesia, with routes to Surabaya, Bandung and Jakarta.

Then, it will be Denpasar in Bali and countless more. Anywhere within three hours flight time from AirAsia's hubs in Kuala Lumpur or Bangkok is game to Fernandes.

"We would love to go to Indochina - Vietnam, Cambodia, places like that."

India and China have also been slated as future destinations from AirAsia's Thai base.

In the longer term, Fernandes does not rule out the possibility that he might succumb to the temptation of shaking up other industries the way Branson did with his expanding Virgin empire. After all, the AirAsia chief experienced it first hand - he once made music videos for the Virgin record label.

"My hands are full right now.(but) I am interested in that (expanding the company's portfolio).

"Definitely music will play a part in my life again. I have been talking to (musician) Peter Gabriel and a few other guys about doing some stuff together. So yes, music will definitely feature."