Η Ellinair ιδρύθηκε το Φεβρουάριο 2013 και ανήκει στον Όμιλο Εταιρειών Mouzenidis Group. Ο συγκεκριμένος όμιλος ιδρύθηκε το 1995 από τον Μπόρις Μουζενίδη και είναι ένας από τους μεγαλύτερους τουριστικούς πράκτορες της Βόρειας Ελλάδας. Την βάση της εταιρίας αποτελεί το αεροδρόμιο «Μακεδονία» της Θεσσαλονίκης.
Τον Οκτώβριο 2013 η εταιρία προχώρησε στην μίσθωση δύο αεροσκαφών τύπου AVRO BAe RJ 85 με σκοπό τα επόμενα έτη να διακινεί το 30% των πελατών της Mouzenidis Travel με αεροσκάφη της Ellinair. Έλαβε την άδεια εκμετάλλευσης από την Υπηρεσία Πολιτικής Αεροπορίας στις 8 Ιανουαρίου 2014. Οι πρώτες πτήσεις άρχισαν τον Φεβρουάριο 2014 στο δρομολόγιο Θεσσαλονίκη – Κίεβο. Η εταιρία δραστηριοποιείτε κυρίως σε πτήσεις από διάφορους προορισμούς της Ρωσίας και Ουκρανίας προς Ελλάδα.
Τον Απρίλιο 2015 η Ellinair ανακοίνωσε την έναρξη πτήσεων και εντός Ελλάδας (από Θεσσαλονίκη και Αθήνα) και προχώρησε στην μίσθωση αεροσκαφών Airbus A319 και Boeing 737-300. Στην πρώτη οικονομική της χρήση (Φεβρουάριος – Δεκέμβριος 2014), η Ellinair παρουσίασε κύκλο εργασιών 22,37 εκατ. € και κέρδη προ φόρων 87 χιλ. €.