H Cretan Airlines (ή Κρητικές Αερογραμμές) ιδρύθηκε το 1992 με έδρα το Ηράκλειο από Κρήτες επιχειρηματίες που δραστηριοποιούνταν στον τομέα του τουρισμού (συγκεκριμένα ήταν ιδιοκτήτες ξενοδοχείων). Σκοπός της εταιρίας ήταν να μεταφέρει με πτήσεις τσάρτερ στην Κρήτη τους πελάτες των ξενοδοχείων των ιδρυτών της
Η αεροπορική εταιρία από την Κρήτη έλαβε άδεια εκμετάλλευσης τον Ιούνιο του 1992 και παρέλαβε το πρώτο της αεροσκάφος, ένα Airbus A320μισθωμένο από την σλοβενική Adria Airways, τον Μάρτιο του 1993. Στις αρχές Απριλίου η εταιρία παρέλαβε και δεύτερο Airbus A320 και στα μέσα του ίδιου μήνα πραγματοποίησε την πρώτη της πτήση. Τα δύο επόμενα χρόνια οι Κρητικές Αερογραμμές πρόσθεσαν επιπλέον δύο Airbus A320 στον στόλο τους.
Άξιο αναφοράς είναι το γεγονός ότι η Cretan Airlines, παρόλο που ιδρύθηκε με σκοπό να εκτελεί ναυλωμένες πτήσεις, είχε ανοίξει ένα σταθερό δρομολογιο μεταξύ Θεσσαλονίκης – Αθήνας – Κρήτης, ενώ σκόπευε να λειτουργήσει επιπλέον δρομολόγια εσωτερικού. Γι’ αυτό τον σκοπό είχε πρόθεση να προμηθευτεί αεροσκάφη τύπου Dornier Do328. Ακόμη, ένα Fokker F100 ήταν να έρθει για την άμεση επέκταση του στόλου και κατ’επέκταση την επιχειρησιακή δυνατότητα της εταιρίας. Ωστόσο τα εν λόγω αεροσκάφη δεν προμηθεύτηκαν ποτέ εξαιτίας των μεγάλων οικονομικών προβλημάτων που σύντομα κλήθηκε να αντιμετωπίσει η εταιρία.
Αιτία του κακού ήταν η χαμηλή πληρότητα που εμφάνιζαν οι πτήσεις των Κρητικών Αερογραμμών ιδιαίτερα κατά τους χειμερινούς μήνες, γεγονός που οδήγησε στην δημιουργία ζημιών στους ιδιοκτήτες της. Τα υπέρογκα χρέη επέφεραν την καθήλωση των αεροσκαφών της Cretan Airlines και εν συνεχεία την ανάκληση της AOC (Air Operation Certificate δηλαδή Πιστοποιητικό Πτητικών Επιχειρήσεων) από την Υπηρεσία Πολιτικής Αεροπορίας τον Απρίλιο του 1995.
Στο διάστημα της λειτουργίας τους οι Κρητικές Αερογραμμές είχαν μεταφέρει συνολικά περισσότερους από 100.000 επιβατες και απασχολούσαν περίπου 250 ατομα. Η εταιρία εκτελούσε ναυλωμένες πτήσεις από αεροδρόμια της Κρήτης προς διάφορες χώρες της Ευρώπης και κυρίως προς Αυστρία, Γερμανία, Γαλλία, Ελβετία, Ιταλία και Ισπανία. Τέλος, ο στόλος της απαρτιζόταν από 4 μισθωμένα Airbus A320 (με στοιχεία νηολογίου SX-BAT, SX-BAS, SX-BAU και SX-BAX) ενώ αξιοσημείωτο είναι το γεγονός ότι η Cretan Airlines υπήρξε η πρώτη ελληνική αεροπορική εταιρία που πέταξε τον συγκεκριμένο τύπο αεροσκάφους!
