Η Hellenic Star Airways Α.Ε. ιδρύθηκε το 1999 απο τον κ. Νικο Βαλαγιάννη και απέκτησε αμέσως Πιστοποιητικό Αερομεταφορέα (AOC), Άδεια Εκμετάλλευσης (OPER. LICENCE) καθώς και Πιστοποιητικό Συντηρήσεως Α/φων (JAR-145) από την Ελληνική Υπηρεσία Πολιτικής Αεροπορίας. Από τον Σεπτέμβριο του 1999 συμμετείχε στην αγορά των Δημοσίων Αερομεταφορών εκτελώντας κανονικά δρομολόγια προς ΣΥΡΟ – ΠΑΡΟ – ΜΥΚΟΝΟ – ΛΕΡΟ και ΙΚΑΡΙΑ καθώς και ναυλωμένες πτήσεις στο εσωτερικό, με ένα τετρακινητήριο αεροσκάφος TURBOPROP DHC-7 48 θέσεων. Κατά τη χρονική διάρκεια της πρώτης περιόδου εκμετάλλευσης (Σεπτέμβριος 1999 – Νοέμβριος 2000) η εταιρεία μετέφερε 45.000 επιβάτες από και προς τους προαναφερόμενους προορισμούς του εσωτερικού και πραγματοποίησε 300 ώρες ναυλωμένων πτήσεων. Από τον Μάρτιο του 2001, η εταιρεία προσανατολίστηκε στην διενέργεια μόνο ναυλωμένων πτήσεων.
Στα επιχειρηματικά σχέδια της HELLENIC STAR AIRWAYS και υπό τις παρούσες συνθήκες που επικρατούσαν τοτε στον κλάδο των αερομεταφορών, αποτυπώνονταν η στρατηγική της σταδιακής ανάπτυξης με αεροσκάφη TURBOPROP και η διατήρηση του χαρακτήρα της εταιρείας, ως “Περιφερειακής Εταιρείας” (Regional Carrier) Εσωτερικών και Διεθνών δρομολογίων μικρών και μεσαίων αποστάσεων. Η πρώτη φάση ανάπτυξης (2002 – 2003) περιελάμβανε την μίσθωση δύο (2) αεροσκαφών Turboprop SAAB 340B 36 θέσεων απο την Mandarin Airlines με διαμεσολαβητη την Skyways Aviation (η οποια ειχε αναλαβει και την μεταπωληση του DHC7), για την εκτέλεση τακτικών δρομολογίων εσωτερικού και εξωτερικού καθώς και σειρών ναυλωμένων πτήσεων στο εσωτερικό και εξωτερικό. Η δεύτερη φάση ανάπτυξης (2003 – 2005) την ανάπτυξη του δικτύου με την μίσθωση τριών (3) αεροσκαφών Turboprop μεγαλύτερης χωρητικότητας (έως 70 θέσεων) ώστε να υπάρξει θετική μετατόπιση της μέσης απόστασης εξυπηρετούμενων προορισμών και ανάληψη μεγαλύτερου αριθμού δρομολογίων εξωτερικού σε όμορες χώρες (ΙΤΑΛΙΑ – ΒΟΥΛΓΑΡΙΑ – FYROM – ΤΟΥΡΚΙΑ – ΛΙΒΥΗ κλπ.), κατι που δεν εγινε ποτε.
Η βάση της εταιρείας ήταν αρχικά το αεροδρόμιο της Σύρου, λόγω και της συνεργασίας με το τοπικό καζίνο, και κατόπιν το Ελευθέριος Βενιζέλος. (Τα γραφεία ηταν Λ. Βουλιαγμενης 2 στο Ελληνικο)
Η τελευταία πτήση της εταιρείας ήταν στις 2 Μαρτίου 2003 η πτήση Αθήνα-Χανιά, με ένα SAAB340. Η τελευταία πτήση του DHC7 στις 6 Ιανουαρίου 2003, η πτήση Θεσσαλονίκη-Αθήνα.
To πρόγραμμα των πτήσεων εσωτερικού της εταιρείας (stand: 18 Ιανουαρίου 2002)
Τα ακόλουθα αεροσκάφη πέταξαν με τα χρώματα της Hellenic Star Airways.