La compagnia aerea era stata fondata ed ha iniziato ad operare il 16 ottobre 1960 come Aeropesca Colombia.
Ha subito diversi incidenti ed è stata venduta ad un gruppo di azionisti che hanno cambiato nome e immagine in Intercontinental de Aviacion nel 1982. Vendettero solo un Vickers Viscount e l'unico Curtiss C-46 Commando che avevano, sostituendoli con un McDonnell Douglas DC-9-15 e un altro Viscount, e nel giugno 1983 iniziò ad operare da Bogotá verso ovest.
Nel 1986 cambiarono i soci, si consolida come società in via di sviluppo e rivaleggiò con Avianca e SAM Colombia. La compagnia aerea cominciò ad operare voli internazionali nel 1991, e nel 1993 comprò altri DC-9-15 e De Havilland DHC-8. La Executive Class e le sale VIP iniziarono ad essere offerte a Bogotá, Cali, Medellín e Barranquilla. Nell'ottobre 2000 sono stati acquistati quattro Beechcraft 1900D, oltre a due Boeing 737-300, che tuttavia non vennero mai utilizzati.
La compagnia aerea si trovò costretta a cessare le operazioni nel settembre 2005 in seguito allo schianto del volo West Caribbean Airways 708 in Venezuela. Dopo l'incidente, l'Autorità per l'aviazione civile colombiana richiese a tutte le compagnie aeree un'ispezione speciale delle sue strutture di manutenzione e degli aeromobili.
4 novembre 1965 - Un Consolidated PBY Catalina (codice di registrazione HK-811) scomparve durante un volo interno. Quattro dei sei occupanti a bordo furono scoperti 9 giorni dopo vicino al confine peruviano.[1]
11 luglio 1966 - Un Curtiss C-46 Commando (codice di registrazione HK-527) scomparve sopra un terreno montuoso durante un volo da Bogotá a Buenos Aires. L'aereo trasportava otto tori per una mostra a Buenos Aires. Tutti gli 8 occupanti a bordo rimasero uccisi.[2]
5 gennaio 1974 - Un Lockheed L-18 Lodestar (codice di registrazione HK-1146) subì un guasto al carrello di atterraggio durante il decollo da Bogotá. L'aereo tornò in aeroporto e cercò di riatterrare, tuttavia i freni non funzionarono, facendolo uscire di pista e fermandosi in un fossato di drenaggio.[3] Tutti e 5 gli occupanti a bordo sopravvissero.
14 agosto 1978 - Un Curtiss C-46 Commando (codice di registrazione HK-1350) che volava in pessime condizioni meteorologiche andò fuori rotta durante un volo da Bogotá a Tame e si schiantò contro il Monte Paramo de Laura vicino a Tota, in Colombia, uccidendo tutte le 18 persone a bordo. Certificato per trasportare solo sei passeggeri, ne aveva caricati 15 al momento dell'incidente.[5]
26 marzo 1982 - Un altro Viscount (codice di registrazine HK-2382) volò contro una montagna vicino a Queate durante un volo dall'aeroporto La Vanguardia all'aeroporto internazionale El Dorado, uccidendo tutte le 21 persone a bordo.[7]
31 marzo 1991 - Il Viscount HK-1708 rimase irreparabilmente danneggiato (dal punto di vista economico) durante un volo dall'aeroporto internazionale El Dorado all'aeroporto internazionale Gustavo Rojas Pinilla. Entrambi gli orizzonti artificiali si guastarono nel mezzo di una turbolenza a 16.000 piedi. I piloti ripresero il controllo dell'aereo a 4.000 piedi, effettuando un atterraggio d'emergenza all'aeroporto Olaya Herrera, a Medellín. Si è scoperto che il longherone principale inferiore si era rotto. Il 14 febbraio 1988 l'aereo aveva subito un collasso del carrello d'atterraggio.[8]
11 gennaio 1995 - Il volo Intercontinental de Aviación 256, un McDonnell Douglas DC-9-14 (codice di registrazione HK-3839X), si schiantò durante l'avvicinamento nei pressi di María la Baja. L'incidente uccise quasi tutti i 52 occupanti tra passeggeri e membri dell'equipaggio, tranne una ragazzina in viaggio con la sua famiglia.
14 settembre 1997 - Un Bombardier Dash 8 Q300 (codice di registrazione HK-4062X) stava operando un volo da San Andrés a Pereira, con scalo a Bogotá. Quando l'aereo atterrò all'aeroporto internazionale di Matecaña, il carrelli d'atterraggio sinistro e anteriore, seguiti dal carrello destro, cedettero.[9][10] Fortunatamente i 39 passeggeri e 5 membri dell'equipaggio sopravvissero. L'aereo rimase irreparabilmente danneggiato e radiato dai registri della compagnia, ma si decise di conservarlo a Bojacá su un terreno agricolo privato come fonte di pezzi di ricambio.
14 giugno 2002 - Un McDonnell Douglas DC-9-14 (HK-3859X) uscì di pista durante l'atterraggio all'aeroporto Benito Salas. Tutti i 65 passeggeri e i 6 membri dell'equipaggio sono sopravvissuti, mentre l'aereo fu radiato.[11]