أنشئت شركة الطيران في 2 أكتوبر 1980، وبدأت أول عملياتها في 20 فبراير 1981 بعدة طائرات صغيرة، حتى اُردفت الشركة بطائرات طراز إمبراير اي إم بي 110 بانديرانتيوفوكر إف27 فريند شيب. عام 1990، سجلت الشركة انخفاضاً في المسافرين بنسبة 9%، لكن ظهور شركة الخطوط الجوية (كوبا أيرلاينز كولومبيا) عام 1992 وضع شركة خطوط الطيران لان كولومبيا في منافسة في السوق الكولومبية، فأجرت الشركة توسيعات صغيرة بإضافة رحلات إلى البلدان المجاورة فنزويلا والإكوادور إضافة إلى الرحلات المحلية. [بحاجة لمصدر]