To όνομα της Blue Star Airlines ακούστηκε για πρώτη φορά στα τέλη Απριλίου 2004. Πίσω από το σχήμα ακούστηκε ότι βρισκόταν ένας ελβετικός όμιλος, η Gemis Group η οποία είχε συνδέσει το όνομα της παλιότερα με την Ολυμπιακή. Θα ήταν μια εταρεία χαμηλού κόστους (no frills) με έδρα τη Θεσσαλονίκη και θα αποκτούσε 4 Airbus A320. Οι πτήσεις ήταν να ξεκινήσουν τον Οκτώβριου του ίδιου έτους, ή στις αρχές Μαρτίου του 2005. Παρόλα ταύτα, η εταιρεία παραδόξως δεν είχε καταθέσει αίτηση για έκδοση άδειας πτητικής εκμετάλλευσης, γιατί όπως ειπώθηκε τότε, "είναι πολύ δύσκολο να πάρει κανείς απαντήσεις από τις ελληνικές υπηρεσίες" - προφανώς οι ιδιοκτήτες είχαν κάνει άσχημες εμπειρίες με την ΟΑ παλιότερα! Μέχρι στιγμης'ειναι άγνωστο που θα κατατίθενταν τα χαρτιά. Επίσης δεν είναι γνωστό εάν η εταιρεία ήθελε να κάνει προγραμματισμένες ή μισθωμένες πτήσεις.
Οι μήνες περνούσαν, νέα δεν υπήρχαν, οι ημερομηνίες αθετήθηκαν. Το όλο "project" προχώρησε μόνο μέχρι τη δημιουργία μιας απλούστατης ιστοσελίδας, screenshot της οποίας βλέπετε πιο κάτω. Η σελίδα εννοείται ότι δεν υφίσταται πλέον.
