The origins of Carnival Air Lines can be traced to 1984 when Pacific Interstate Airlines was founded in Las Vegas, Nevada. This airline flew charters between Las Vegas and Los Angeles. In 1985 the name was changed to Pacific Inter Air and then only two years later the name was changed to Bahamas Express. By this time the airline was flying out of airports in the East Coast of the USA to Freeport in the Bahamas. Carnival Cruise Lines bought the company in 1988 and the airline's name was once again changed to Fun Air, but no planes were painted with that name and cruise ship passengers were flown by Majestic Air using a Boeing 727-100 jetliner.
The final identity of Carnival Air Lines came to being in 1989 and the airline began flying from Miami, the Northeast USA and later on expanded to other destinations. The home base for Carnival Air Lines was Ft. Lauderdale, Fl. (See routes below).
In 1992 Carnival Air Lines began a code-share agreement with Iberia Airlines of Spain to transport connecting passengers from Madrid to Los Angeles via Carnival's Miami Hub. The route was originally operated by a Boeing 737-400 but was replaced in 1994 with Carnival's first Airbus A300. In 1993 Carnival began operating its first wide-body aircraft by flying LanChile's Boeing 767 as part of the interchange agreement with the Chilean airline. The exclusive route was from Miami to New York's JFK airport. In 1995 when the agreement with LanChile was not renewed, another agreement was formed with LADECO of Chile to transport connecting passengers from Santiago to New York via Carnival's Miami Hub flying a Carnival Airbus A300 in LADECO's livery.
In September 1997, Pan Am Corp., a holding company formed by the reincarnated Pan American Airways (1996-1998), bought Carnival Air Lines in an attempt to bolster its fleet and operations into a new airline based on the old Pan Am. Before the airlines could fully merge, the holding company and its two independently operated airlines, Pan Am and Carnival, filed for bankruptcy protection and ceased scheduled flight operations in February 1998. The operating certificate used for the first reincarnated Pan Am was abandoned in favor of the acquired Carnival operating certificate. Pan Am, now operating with the Carnival certificate, quickly resumed limited charter operations while new owner Guilford Transportation Industries of Massachusetts acquired certain assets of the bankrupt companies after court approval. The new company emerged from bankruptcy in June 1998 and discontinued the use of the Carnival Brand name for the Pan Am name and logo instead. Guilford ceased operating Pan Am and relinquished its original Carnival airworthiness certificate on November 1, 2004. Operations were transferred to Boston-Maine Airways, which resumed 727 service under the "Pan Am Clipper Connection" brand from February 17, 2005.
Its IATA code has now been reassigned to Wataniya Airways.