בינואר 1997חברת התעופה הלאומית של ונצואלה, ויאסה, הפסיקה את פעולותיה לאחר 37 שנות שירות, מטעמים כלכליים. במאי 2001 עלתה ההצעה ליצור חברת דגל חדשה לוונצואלה, וב-30 במרץ2004 נשיא ונצואלה הוגו צ'אווס חתם על צו כדי ליצור באופן רשמי את חברת התעופה החדשה קונביאסה. ב-28 בנובמבר ערכה החברה את טיסת הבכורה שלה וב-10 בדצמבר החלה החברה את פעולתה עם טיסות סדירות פנימיות ובינלאומיות.