Nel 1967, Conrad "Connie" Kalitta iniziò, come Connie Kalitta Services, un'attività di trasporto di parti di automobili utilizzando un Cessna 310 bimotore da lui pilotato.[4] La compagnia divenne in seguito American International Airways. AIA iniziò le operazioni nel 1984 utilizzando Boeing 747, Lockheed L-1011, Douglas DC-8, Twin Beech e Learjet, per operazioni charter di trasporto passeggeri e merci e servizi di aeroambulanza.
Durante la fine degli anni '80, il marchio Kalitta continuò ad apparire su molti degli aerei cargo della compagnia. Nel 1990 e nel 1991, AIA effettuò 600 missioni a sostegno delle operazioni Desert Shield e Desert Storm.
Nel 1997, AIA si fuse con Kitty Hawk Inc. e Conrad Kalitta si dimise per avviare Kalitta Leasing per l'acquisto, la vendita e il leasing di aeromobili di grandi dimensioni. Nell'aprile 2000, Kitty Hawk International (l'ex AIA) cessò le operazioni. Kalitta decise di salvarla e la nuova compagnia aerea, Kalitta Air, iniziò le operazioni nel novembre 2000, utilizzando il certificato operativo e le risorse della precedente compagnia aerea.
Il 21 aprile 2017, Kalitta Air ha ritirato il suo ultimo Boeing 747-200F dal servizio.[5][6]
Kalitta Maintenance gestisce una struttura di manutenzione, riparazione e revisione presso l'aeroporto di Oscoda – Wurtsmith nella contea di Iosco, Michigan.
Il nome American International Airways è stato utilizzato anche da una compagnia aerea che nel 1981 operava da un hub situato presso l'aeroporto Internazionale di Filadelfia con un servizio non-stop per Atlantic City, Boston, Chicago Midway, Cleveland, Detroit, Fort Lauderdale, Miami, Norfolk , Orlando, Pittsburgh, Tampa e West Palm Beach utilizzando jet come i Douglas DC-9-30 e i McDonnell Douglas MD-80. La società dichiarò fallimento il 19 luglio 1984 e cessò le attività a settembre.[7]
Il 25 maggio 2008, il volo Kalitta Air 207, un Boeing 747-200F, era in corsa di decollo da Bruxelles. La fase iniziale fu tranquilla. La velocità aumentò con un'accelerazione costante fino a quando uno dei motori subì una momentanea perdita di potenza. Questo fenomeno venne accompagnato da un forte scoppio, udito dall'equipaggio e da testimoni esterni, e da fiamme, viste dalla torre di controllo. Il botto e la perdita di potenza si verificarono intorno alla velocità V1. Due secondi dopo, tutti e quattro i motori vennero riportati al minimo e i piloti iniziarono a frenare. Gli inversori di spinta non vennero utilizzati. L'aereo si fermò 300 metri dopo la fine della pista 20, sopra un terrapieno ferroviario. L'aereo venne gravemente danneggiato; si ruppe in tre parti.[14]
Il 7 luglio 2008, Il volo Centurion Air Cargo 164, un Boeing 747-200(SF) operato dalla Kalitta Air, precipitò poco dopo il decollo. Tutti a bordo rimasero feriti, ma nessuno rimase ucciso. Due persone a terra persero la vita dopo che l'aereo si era schiantato contro una fattoria. L'incidente fu il secondo di un Boeing 747 di Kalitta Air nel 2008, dopo un precedente incidente a Bruxelles a maggio. Un'indagine venne avviata dalle autorità colombiane e concluse che l'incidente era stato causato da un guasto a due motori. Durante la fase di decollo, il motore n.4 e poi il motore n.1 avevano subito una perdita di potenza.[15]