Flagship Airlines faceva risalire le sue origini ad Air Virginia, un vettore aereo per pendolari e feeder regionale, che in seguito cambiò nome in AVAir. AVAir fallì rapidamente in seguito alla tragedia del volo AVAir 3378. AMR Corporation fondò la Nashville Eagle dalle attività di AVAir e Air Midwest. Flagship Airlines è stata costituita dalla fusione di Command Airways in Nashville Eagle il 1 giugno 1991.
La società madre American Airlines operava dei voli in code sharing con il marchio American Eagle. La compagnia aerea serviva la costa orientale e le Bahamas dagli hub di Miami, Nashville, New York-JFK e Raleigh/Durham. La sede di Raleigh/Durham è stata chiusa il 28 dicembre 1994.[1]
Alla fine, Flagship Airlines si fuse con Simmons Airlines e Wings West Airlines per formare American Eagle Airlines nel 1998. L'ex codice IATA MQ della Simmons divenne così l'identificatore sopravvissuto per le compagnie aeree unificate. Nel 2014, la compagnia aerea è stata ribattezzata Envoy Air.