Im Juli 1981 wurde Muse Air gegründet. Der Begründer, Lamar Muse war in der Luftfahrtbranche kein Unbekannter, denn er war maßgeblich am Auf- und Ausbau der bekannten Southwest Airlines beteiligt.
Nachdem L.Muse 1978 nach einem Streit mit dem Aufsichtsrat von Southwest die Airline verlassen hatte trieb er den Aufbau seiner eigenen Fluggesellschaft voran und wollte in direkter Konkurrenz zur Southwest treten.
Als Heimatbasis wurde Dallas Love Field ausgewählt und von da aus flog man ab Juni 1982 mit zwei neuen McDonnell Douglas MD-82 nach Houston. Erweitert wurden die Destinationen noch nach Austin, New Orleans, Lubbock, Midland/Odessa und Tulsa. Außer MD-82 setzte Muse Air ab Oktober 1983 gebrauchte Maschinen vom Typ Douglas DC-9-51 ein.
Durch ein Abkommen mit AIR CAL erweiterte sich das Streckennetz bis nach Las Vegas und Los Angeles, wo Anschlußflüge durch AIR CAL bis in den Norden der USA angeboten wurden. Das eigene Streckennetz erweiterte sich ebenfalls und so wurde Miami und San Francisco in den Flugplan aufgenommen.
MUSE AIR hatte im Gegensatz zur Southwest ihre Flugzeuge als Erste Klasse Flüge angeboten, aber die Auslastung der Maschinen ließ stark zu wünschen übrig. Wie das Schicksal so spielt, kauft im Februar 1986 gerade Southwest Airlines die inzwischen marode Gesellschaft auf und änderte den Namen in Transtar Airlines.