Gegründet von Yachthandel- und Charterspezialisten Urs-Peter Furrer nahm die Air-Sea Service noch in ihrem Gründungsjahr, am 31. Oktober 1974 den Flugbetrieb mit einer Britten-Norman BN-2A "Islander" auf. Neben Taxi- und Geschäftsflügen wurde bereits im Sommer 1976 mit einer regel-mässigen Verbindung zwischen Basel-Mulhouse und Luxembourg begonnen. Dies war jedoch nicht nur der Swissair ein Dorn im Auge und so verwunderte es nicht, dass der Bundesrat in letzter Instanz anfangs 1978 der Air-Sea Service die beantragten Streckenrechte nach Luxembourg verweigerte. Man befürchtete nämlich ein Abwandern von Passagieren auf die billigen Linienkurse der damaligen Loftleidir nach Island und den Vereinigten Staaten.

Ebenfalls 1976 wurden im Hinblick auf einen Ausbau der Aktivitäten von der belgischen Delta Air Transport (DAT) zwei Convair CV-440 "Metropolitan" erworben, von denen jedoch aus verschiedenen Gründen nur eine, die spätere HB-IMU übernommen wurde. Nachdem Swissair auf den Sommerflugplan 1978 ihre Linienverbindung Genève – Basel-Mulhouse – München einstellte, bemühte sich Air-Sea Service um eine entsprechende Linienkonzession nach der bayrischen Hauptstadt. Etwas überraschend wurde die Genehmigung auch erteilt und ab Juni 1978 durfte die kleine "Islander" bereits montags, mittwochs und freitags je zweimal linienmässig nach München und zurück fliegen. Air-Sea Service war es somit als erster Schweizer Fluggesellschaft gelungen, das Linienmonopol der Swissair zu durchbrechen. Weitere Liniengesuche für Flüge ab Basel-Mulhouse nach Frankfurt, Düsseldorf, Luxembourg und Mailand-Linate wurden hingegen abgelehnt. Um den Kunden einen verbesserten Komfort zu bieten, liess sich Air-Sea Service nach dem Aérosalon von Paris-Le Bouget 1978 eine australische GAF "Nomad 22" vorführen. Durch den günstigen Anschaffungspreis von rund 1,5 Millionen Schweizerfranken wurde umgehend eine etwas grössere GAF "Nomad 24A" mit 18 Plätzen zur Auslieferung im März 1979 in Auftrag gegeben. Die Vorführmaschine wurde gleich behalten und ersetzte auf der nun bereits werktäglich bedienten München-Route die neunsitzige BN-2A "Islander". Erfolgreich waren anfangs 1979 auch die Bemühungen die Convair CV-440 "Metropolitan" auf Städteflügen einzusetzen. Im Auftrag von Imholz-Reisen konnten ab Zürich drei wöchentliche Rotationen nach Venedig, Olbia und Ibiza durchgeführt werden. Immerhin konnten somit von Mai bis Oktober gegen 550 Flugstunden absolviert werden. Bisher war die Maschine höchst selten im Einsatz, dies hauptsächlich auf Messeflügen und auf Skichartern nach Samedan und Innsbruck. Ende 1979 standen grössere Wartungs- arbeiten an der "Metropolitan" an und Air Sea-Service bemühte sich die Maschine zu veräussern und durch eine Convair CV-580 oder Hawker-Siddeley 748 zu ersetzen. Dazu musste allerdings das finanzschwache Unternehmen saniert und eine Kapitalerhöhung angestrebt werden.

Nach zähen Verhandlungen konnte die Convair CV-440 "Metropolitan" für knapp 100'000 Schweizerfranken an einen Flugzeughändler in den USA verkauft und die GAF Nomad 24A über das australische Herstellerwerk an das Internationale Komitee des Roten Kreuz (IKRK) vermietet werden. Als Ersatz wurden von der französischen Tourraine Air Transport (TAT) für bereits damals überhöhte 3 Millionen Schweizerfranken zwei Nord 262B mit je 29 Sitzen gekauft, welche im August und Oktober 1980 nach Basel-Mulhouse geliefert wurden. Nach einer Grundüberholung und Modernisierung durch den technischen Dienst der Balair konnte die erste Maschine am 1. November 1980 ihre Dienste auf den Linienflügen nach München aufnehmen. Im April 1981 konnte Rhineair eine Nord 262B an Balair vermieten, welche sie direkt an die Vereinten Nationen (UNO) weitergab, da sich deren von Balair betriebene Fokker F. 27 "Friendship" in Basel-Mulhouse einer mehrwöchigen Wartung unterzog. Die nächste Krise kam bereits wenige Monate später, nachdem die Gesuche für weitere Linienverbindungen ab Basel-Mulhouse nach Destinationen in Deutschland, Frankreich und Italien weiderum nicht gewährt wurden. Das Aktienkapital musste erneut herabgesetzt werden, diesesmal auf 135'000 Schweizerfranken und die Betriebskonzession wurden vom Bundesamt für Zivilluftfahrt (BAZL) nur noch provisorisch bis Ende März 1982 erteilt. Noch einmal konnte das Kapital auf rund 1,6 Millionen Schweizerfranken erhöht werden, doch folgte der finanzielle Absturz umgehend, konnten doch die für den Winter 1981/82 vorgesehene Skicharterketten nach Sion allesamt nicht durchgeführt werden.

Am 1. März 1982 musste Rhineair den Betrieb einstellen und bereits am Tag darauf erfolgte der Gang zum Konkursamt Basel-Stadt. Das Unternehmen soll einen Schuldenberg von etwa 4,5 Millionen Schweizerfranken hinterlassen haben. Die Linienkonzession wurde am 4. März dem BAZL retourniert, dies nachdem mit der Crossair Verhandlungen geführt wurden, neben dem Personal, auch die Linien- rechte und sogar die beiden Nord 262B zu übernehmen. Einmalmehr war eine Schweizer Fluggesellschaft an zuwenig Eigenmitteln, falscher Flottenpolitik und wenig kompetentem Management gescheitert. Bereits einige Tage später konnte Crossair tatsächlich die Flüge nach München übernehmen und sogar auf drei tägliche Kurse aufstocken. Zum Einsatz kamen allerdings die eigenen Swearingen "Metroliner II".

Flotte: