Οι Μακεδονικές Αερογραμμές ήταν θυγατρική εταιρία της Ολυμπιακής Αεροπορίας. Δεν είχε καμία σχέση με την MAT-Macedonian Airlines των Σκοπίων. Οι Μακεδονικές Αερογραμμές ιδρύθηκαν το 1992, αλλά οι πρώτες πτήσεις της εταιρίας έγιναν το 1998 με παλαιά αεροσκάφη τύπου Β727-200 της Ολυμπιακής. Οι Μακεδονικές Αερογραμμές απέκτησαν το 1999 τα πρώτα «δικά» τους αεροσκάφη, δύο Β737-400. Με αυτά τα αεροσκάφη άρχισαν να εκτελούν πτήσεις τσάρτερ, ενώνοντας τα ελληνικά νησιά με Ευρωπαϊκούς προορισμούς. Το 2000 η εταιρία παρέλαβε ένα επιπλέον Β737-400 με 167 θέσεις.
Οι Μακεδονικές Αερογραμμές είχαν συνάψει συμφωνίες με διάφορους μεγάλους τουριστικούς ομίλους της Ευρώπης (οι συμφωνίες ίσχυαν και μετά την ίδρυση των Ολυμπιακών Αερογραμμών). Την συντήρηση των αεροσκαφών των Μακεδονικών Αερογραμμών είχε αναλάβει η τεχνική βάση της Ολυμπιακής. Τα έτη 2002 και 2003, τα αεροσκάφη των Μακεδονικών εκτελούσαν πολλά τακτικά δρομολόγια της μητρικής εταιρίας, λόγω έλλειψης αεροσκαφών στην Ολυμπιακή. Γι΄ αυτό το λόγο οι Μακεδονικές προχώρησαν σε μίσθωση δύο αεροσκαφών τύπου MD-82, μαζί με πλήρωμα (wet-lease).
Από την 12 Δεκεμβρίου 2003 οι Μακεδονικές Αερογραμμές μετονομάστηκαν σε Ολυμπιακές Αερογραμμές και αυτή η νέα εταιρία εκτελούσε έως την ιδιωτικοποίηση των Ολυμπιακών Αερογραμμών το πτητικό έργο των εταιριών Ολυμπιακή Αεροπορία (Olympic Airlines), Αεροπλοΐα (Olympic Aviation) και Μακεδονικές Αερογραμμές. Περισσότερα στο τμήμα των Ολυμπιακών Αερογραμμών.
