החברה נוסדה בשנת 1991 בשם ארבריה איירליינס, והייתה בתחילתה חברה פרטית של פוליטיקאים באלבניה הקומוניסטית. במאי 1992 שינתה את שמה לאלבניאן איירליינס. בשנת 1995 פתחה לראשונה את טיסותיה לציבור הרחב. החברה הפסיקה את פעילותה ב-2011, לאחר שרשות התעופה האלבנית ביטלה את רישיון ההפעלה שלה.
טירנה, אלבניה
אתר האינטרנט הרשמי של אלבניאן איירליינס