H AirSea Lines [ κωδικοί - / PEV] ιδρύθηκε στις αρχές του 2003, με σκοπό να παράσχει το πρωτοποριακό (για τα ελληνικά δεδομένα) προιόν του υδροπλάνου. Πρόεδρος της ήταν ο κ. Πατέλης. Μέτοχοι της εταιρείας ήταν δύο επενδυτικά fund, η Rab Capital με ποσοστό συμμετοχής 17,16% και η Fidelity με 9,56%. Επίσης δεύτερος μεγαλομέτοχος ήταν ο καναδός Thomas Grenville με ποσοστό συμμετοχης στα 12,62%. Τον Μάρτιο του 2003 σιγούρεψε τη συνεργασία με την Harbour Air, τον παγκοσμίως μεγαλυτέρο χρήστη υδροπλάνων και άρχισε τις συνομιλίες για την αδειοδότηση από την ΥΠΑ τον Απριλίο του ίδιου έτους. 'Οπως ήταν φυσικό και λογικό για μια μεσογειακή χώρα οι δημόσιες υπηρεσίες λειτούργησαν και στην περίπτωση της εταιρείας αυτής με ρυθμούς χελώνας, δίνοντας μεν την άδεια αρχές Σεπτεμβρίου 2004 μεν, βάζοντας όμως πολλά άλλα εμπόδια δε. Η εταιρεία για να μπορεσει να λειτουργήσει μέχρι να πάρει την δική της άδεια, είχε αγοράσει τον Δεκέμβριο του 2003 την Pegasus Aviation (αριθμός AOC GR-05, εκδοθέν στις 27.03.2003), μια μικρή εταιρεία aerotaxi με σχεδόν μηδενική πτητική λειτουργεία αλλά δική της άδεια. Τον κωδικό της τον κράτησε και μετά που πήρε τη δική της άδεια και άρχισε τις πτήσεις στις 21 Σεπτεμβρίου 2004, ενώ την άδεια την είχε αποκτήσει ήδη από τον Μάρτιο του έτους. Τον Μάϊο έφτασε στην 'Ελλαδα το πρώτο αεροσκάφος DeHavilland DHC-6 Twin Otter 300 με νηολόγιο SX-BMG το οποίο σύντομα πήρε λευκό χρώμα και πέταξε για ενα διάστημα για τα Ηνωμένα 'Εθνη.
Από την αρχή είχε να αντιμετωπίσει πολλές γραφειοκρατικές δυσκολίες, αλλά και την καχυποψία του 'Ελληνα επιβάτη. Οι αρχές έβρισκαν όλο και νέες δικαιολογίες για την καθυστέρηση στην πιστοποίηση υδατοδρομίων, παρουσιάζοντας «μελέτες» από το πουθενά, στις οποίες στην ουσία σκάλωνε η αδειοδότηση. Πολλοί από τους επίδοξους επιβάτες κατακρίνανε την εταιρεία για το μικρό μέγεθος του αεροσκάφους, για την τιμολογιακή πολιτική της, αλλά και για τα προβλήματα ανάπτυξης που παρουσίαζε, σα να ήταν αποκλειστικά δικιά της ευθύνη! Παράλληλα, τα δημοσιεύματα στον ημερήσιο (μη ειδικό) τύπο έδιναν και έπαιρναν για τις «κοσμογονικές αλλαγές» που έπρεπε να γίνουν στη νομοθεσία για να λειτουργήσει η εταιρεία απρόσκοπτα, ενώ υπουργοί της εποχής για λόγους public relations και μόνο κάνανε πτήσεις με την εταιρεία συνοδευόμενοι από τους... γνωστούς, μοιράζοντας υποσχέσεις και όνειρα. Παρά τις δυσκολίες που αντιμετώπιζε, είχε καταφέρει να αναπτύξει υδατοδρόμεια στην Πάτρα, τους Παξούς, την Κέρκυρα, τη Λευκάδα, το Λαύριο, την 'Ιω, ενώ πετούσε και προς Μπρίντιζι, Ιωάννινα, Ιθάκη, Κάλυμνο, Κεφαλονιά. Για να συμπληρώσει το πτητικό της έργο πρόσεφερε και υπηρεσίες τσάρτερ προς Αλβανία, Ελλάδα, Ιταλία και Τουρκία, τονίζοντας ότι τα αεροσκάφη μπορούν να προσγειωθούν και σε κανονικά αεροδρόμια.
Στις 7 Νοεμβρίου 2006 ένα Twin Otter της εταιρείας προσγειώθηκε στα Royal Victoria Docks στον Τάμεση του Λονδίνου, ως κορύφωμα μιας μελέτης που θα αποδείκνυε τη δυνατότητα χρήσης του πτητικου αυτού μέσου στον ποταμό. Απότερος σκοπός ήταν η χρήση έως και 50 αεροσκαφών της εταιρείας στους Ολυμπιακούς Αγώνες του Λονδίνου, το καλοκαίρι του 2012. Για αυτόν τον σκοπό η καναδική Viking Air αγόρασε τα δικαιώματα από την Bombardier για την κατασκευή των αεροσκαφων.
Το καλοκαίρι του 2007 η βάση από το λιμάνι του Πειραιά μεταφέρθηκε στο Λαύριο, κατι που δυσαρέστησε πολλούς υποψήφιους πελάτες, λόγω της σχετικά περιορισμένης οδικής σύνδεσης με την Αθήνα. Η κίνηση αυτή έγινε σε μια προσπάθεια να αποφευχθούν επιπλέον γραφειοκρατικά προβλήματα. Ως αποτέλεσμα της κίνησης αυτής ήταν η εταιρεία να αναγκαστεί να σταματήσει τις πτήσεις της προς τα Ιόνια νησιά.
Η κατάσταση συνεχίστηκε για 4 συνολικά χρόνια. Το χειμώνα τα αεροσκάφη συνήθως πήγαιναν για ενοικίαση στα H.E. ή την Ελβετία, μιας και οι συνθήκες για πτήσεις στην Ελλάδα δεν ήταν οι ιδανικότερες. Τελικά οι επενδυτές κουρασμένοι από την αδιαφορία αλλά και τη λαιμαργία του ελληνικού γραφειοκρατικού κατεστημένου (όπως είχε δηλωθεί τότε) παράτησαν το πρότζεκτ τέλη Αυγούστου 2008 (αν και οι φήμες λένε ότι πρακτικά η εταιρεία "είχε παραδώσει τα όπλα" από την άνοιξη του ίδιου έτους), έχοντας επενδύσει στην εταιρεία πάνω απο 20 εκατομμύρια €.
Με την παρουσία της, τους αγώνες για επιβίωση και τα όσα κατάφερε η εταιρεία αντιτιθέμενη σε ένα εχθρικό δημόσιο μηχανισμό, και αντιμέτωπη με τα συμφέροντα των πλοιοκτητών οι οποίοι σοβαρά φοβόταν ότι θα χάνανε μεγάλα ποσοστά σε επιβάτες, άνοιξε τον δρόμο για άλλες παρόμοιες εταιρείες.
Τα αεροσκάφη της εταιρείας κατέληξαν στην Μάλτα, με γαλλικό νηολόγιο αλλά με ASL χρωματισμό. Το νηολόγιο του SX-GIK αλλάχθηκε εκεί μόλις τον Μάϊο του 2009. Τα υπόλοιπα νηολογήθηκαν στην Μάλτα όπου και συνεχίζουν να πετάνε σήμερα (άνοιξη 2012) διατηρώντας σχεδόν στο ακέραιο τα χρώμματα της ASL.
Tα εξής αεροσκάφη πέταξαν με τα χρώματα της εταιρείας:
