Η Ολυμπιακή Αεροπλοΐα ήταν μια θυγατρική της Ολυμπιακή Αεροπορίας-Υπηρεσίες Α.Ε. και εκτέλεσε την πρώτη της πτήση τον Αύγουστο του 1971. Ο βασικός στόχος της εταιρίας ήταν, να συνδέει τα ελληνικά νησιά με την ηπειρωτική Ελλάδα. Για αυτόν ακριβώς το σκοπό η εταιρία είχε ένα στόλο από μικρά regional αεροσκάφη με τα οποία μπορούσε να προσεγγίσει σχεδόν κάθε αεροδρόμιο της χώρας.
Στις αρχές 2000 η Αεροπλοΐα μίσθωσε και τα πρώτα αεροσκάφη τύπου jet, δύο Β717-200 με 100 θέσεις επιβατών. Τον Ιανουάριο του 2001 ήρθε ένα επιπλέον Β717-200. Με αυτά τα αεροσκάφη η Αεροπλοΐα άρχισε να εκτελεί και πτήσεις προς το εξωτερικό. Μέχρι τέλη Μαρτίου 2002 η έδρα των αεροσκαφών αυτών ήταν το αεροδρόμιο Μακεδονία της Θεσσαλονίκης. Μετά την ανασυγκρότηση του Ομίλου το 2003, σχεδόν όλα τα αεροσκάφη της εταιρίας πέρασαν στις Ολυμπιακές Αερογραμμές. Μόνο ο στόλος των ελικοπτέρων έχει μείνει στην Ολυμπιακή Αεροπλοΐα, με τον οποίο εκτελεί και πτήσεις charter εάν ζητηθεί.
