H εταιρεία «Αλέξανδρος Ο Μέγας Αεροπορική & Τουριστική ΑΕ», με το απλό διακριτικό Alexandair [ κωδικοί - / AXN ], ιδρύθηκε το 2004 από τον πρώην συνιδρυτή της Cronus Airlines (1995) και Galaxy Airways (1999) κ. Κοκμοτό που ήταν πρώην χειριστής της Πολεμικής Αεροπορίας. Τα αρχικά σχέδια προέβλεπαν την έναρξη των (charter) πτήσεων τον Ιούλιο του 2004 με 2 σκάφη τύπου Boeing B737-400. Για κάποιους μη κοινοποιημένους και αδιευκρίνιστους όμως λόγους, το αεροσκάφος, ένα McDonnell Douglas MD-82 (SX-BMP, cn 49279/1230), δε μισθώθηκε παρά μόνο τελη Ιανουαρίου 2005, ενώ το ίδιο το αεροσκάφος έφτασε σε ελληνικό έδαφος την 26η Απρίλου του ίδιου έτους. Την τεχνική συντήρηση του αεροσκάφους είχε αναλάβει η SAS Technical Service στο αεροδρόμιο Arlanda. Οι πληρότητες στις αρχές της λειτουργίας της εταιρείας μπορούν να χαρακτηριστούν καλές. Σύντομα άρχισαν τα προβλήματα με το αεροσκάφος, το οποίο έμεινε αρχικά για μια μέρα καθηλωμένο στο έδαφος με εντολή της ΥΠΑ στις 20 Αυγούστου 2005, λόγω του ότι κριθηκε τεχνικά ακατάλληλο. Την επόμενη μέρα η εταιρεία έλαβε και παλι AOC περιορισμένης διαρκείας μέχρι το τέλος του μήνα από την ΥΠΑ. Παράλληλα και λίγο νωρίτερα οι γαλλικές αρχές είχαν απαγορεύσει τις πτήσεις της εταιρείας προς Γαλλια, για λόγους τεχνικής ασφάλειας. Στην έκθεση FILOXENIA 2005, η εταιρεία παρουσίασε ένα νέο όνομα και δη „Alexandros Airlines“. Το όνομα αυτό δεν μεταφέρθηκε ποτέ ουτε στην ιστοσελίδα, ούτε και στο αεροσκάφος. Οι πρώτες φήμες για την καθήλωση της εταιρείας λόγω χρεών, ακούγονται στους αεροπορικούς κύκλους το χειμώνα του 2005. Αρχές Δεκεμβρίου 2005 όμως ανακοινώνεται η πρόθεση της εταιρείας για εκτέλεση ναυλωμένων πτήσεων από Θεσσαλονίκη προς Μόναχο, αρχής γενομένης την 17.12.2005. Στα τέλη του ίδιου μήνα τα σχέδια διαγράφονται γιατί δεν υπήρξε συμφωνία με το τοπικό γραφείο Stefan Reisen. Τον Ιανουάριο του 2006 μαθαίνεται οτι η εταιρεία θα χρησιμοποιεί για τους επόμενους 3 μήνες σαν βάση τη Θεσσαλονίκη και όχι το Ηράκλειο. Τον Οκτώβριο του 2006 διαρρέει οτι τα πληρώματα έχουν να πληρωθούν απο τον Αύγουστο του ίδιου έτους. Πολλά ακούγονται, χωρίς να είναι κανεις σιγουρος για τιποτε. Το Νοεμβριο του 2006 το αεροσκαφος παει Σουηδια για συντήρηση και μένει εκεί από τον Φεβρουάριο μέχρι τον 'Αυγουστο του 2007 σε αποθήκευση. Η εταιρεία υπάρχει πλέον μόνο στα χαρτιά και κλείνει αρχές καλοκαιριού 2007 ενώ το αεροσκάφος πηγαίνει στην KhorsAir. Η εταιρεία ήταν από τους λόγους που πολλοί σε αεροπορικούς κύκλους μιλούσαν για «αρπαχτές» και εξαπάτηση, κυρίως λόγω της έλλειψης οργάνωσης, των διάφορων προβλημάτων, οικονομικής και τεχνικής φύσεως.
Η εταιρεία εκτελούσε ναυλωμένες πτήσεις από Αθήνα, Κέρκυρα, Θεσσαλονίκη, Ηράκλειο προς κάθε δυνατό ευρωπαικό προορισμό, όπως: Μπολόνια, Βαρσοβία, Πόζναν, Γκραζ, Ντύσσελντορφ, Λυόν, Βάστερας (Σουηδια), Πάλμα ντε Μαγιόρκα, Στουτγκάδη, Μάντσεστερ, Βιέννη, Λονδίνο, Αννόβερο, 'Αμστερνταμ, Κοπεγχάγη, Νάντη, Βερολίνο, Λιουμπλιάνα, Ρώμη, Βρέστη, Ελσίνκι, ενώ πρέπει να είχε εκτελέσει και κάποιες πτήσεις προς Μέση Ανατολή.
Η εταιρεία είχε μόνο ένα αεροσκάφος στη διάθεση της:
