Η Air Miles άρχισε να εκτελεί δρομολόγια στα μέσα Ιουνίου 2002 με ένα αεροσκάφος τύπου Boeing 737-400. Τα κεντρικά γραφεία της εταιρίας ήταν στην Αθήνα, παρόλα αυτά τα περισσότερα δρομολόγια εκτελούνταν από τα νησιά της Ελλάδας. Αρχικά η εταιρία χρησιμοποιούσε τον χαρακτηριστικό κωδικό ΗΗ της Islandsflug για τις πτήσεις της, μετά την συμφωνία συνεργασίας με την Hellas Jet /2005) οι πτήσεις εκτελούνταν με τον κωδικό Τ4 της τελευταίας.
Αρχικά η εταιρία διέθετε ένα αεροσκάφος τύπου Β737-400. Το συγκεκριμένο αεροσκάφος το είχε μισθώσει από την Islandsflug και στις αρχές 2004 είχε δοθεί στην Ryanair για να επιστρέψει όμως μετά από περίπου τρεις μήνες για την θερινή περίοδο 2004.
Στα τέλη Ιουνίου 2005 η εταιρία υπέγραψε συμφωνία με την Hellas Jet, θυγατρική εταιρία των Κυπριακών Αερογραμμών με βάση της οποίας η Air Miles ανέλαβε την εμπορική εκμετάλλευση των αεροσκαφών της Hellas Jet. Η συμφωνία προέβλεπε, μεταξύ άλλων, δικαίωμα της Air Miles για αγορά του 51% των μετοχών της Hellas Jet από τις Κυπριακές Αερογραμμές, καθώς επίσης και δικαίωμα των Κυπριακών Αερογραμμών για πώληση προς την Air Miles των μετοχών αυτών.
Πρόεδρος και Διευθύνων Σύμβουλος είναι ο κ. Δημήτριος Μάραντος. Περισσότερα για την συνεργασία Hellas Jet - Air Miles στο τμήμα για την Hellas Jet.
