Im Juni 1997 wurde Air Zarco unter den Markennamen Air Madeira vom portugiesischen Reiseveranstalter „Pestana Hotels“ gegründet.
Mit einer von TAP stammenden Lockheed L-1011-500 nahm man von der Heimatbasis in Lissabon den Charterflugbetrieb auf. Die ersten Ziele waren Nürnberg, Amsterdam, Stuttgart, Glasgow und New York.
Die TriStar war unauffällig lackiert und trug keinen Namen am Rumpf. Das änderte sich erst 1999 und der Name Air Zarco wurde am Flugzeug angebracht.
In dem Jahr gelangte für fünf Monate eine Boeing B-737-300 zur Gesellschaft, um auch Kurz- und Mittelstrecken abdecken zu können.
Als man die Linienflugrechte bekam, flog die Airline nun auch nach London Heathrow, Palma de Mallorca und Malta.
Ab dem Jahr 2000 änderte man die Firmenpolitik und nahm erneut eine B-737-300 in die Flotte auf.
Der Name Air Zarco wurde am 17.5.2000 zugunsten des neuen Marktauftrittes Euro Atlantic Airways aufgegeben.