Im September 1971 wurde diese Regionalfluggesellschaft mit Sitz  in Tucson, Arizona gegründet.
Mit einer DeHavilland Canada DHC-6, drei Cessna-402 und einer Beech Sierra baute man innerhalb kürzester Zeit ein dichtes Streckennetz auf und bediente 14 Städte und Gemeinden.
Darunter waren Flagstaff, Douglas/Bisbee, Fort Huachuca/Sierra Vista, Grand Canyon, Kingman, Lake Havasu-Parker, Nogales, Phoenix, Prescott und Yuma.
Ab 1979 kam eine zweite DHC-6 sowie eine Swearingen Metro zur Flotte und man konnte Blythe, Gallup, Winslow, San Diego und Los Angeles ins Streckennetz einbinden.
Ein Jahr später gelangte die erste von insgesamt drei Convair CV-440 zur Gesellschaft.
1981 schloss man mit Saab einen Vertrag über die Lieferung von drei SF-340 ab, die jedoch nicht mehr zur Auslieferung gelangten, denn Cochise Airlines musste im Juni 1982 sämtliche Aktivitäten einstellen und meldete Konkurs an.