Wie schon bei der ALM Antillean Airlines war die niederländische KLM bei der Gründung der staatlichen Air Aruba stark involviert.
Diese Gesellschaft wurde im September 1986 aus der Taufe gehoben und hatte ihre Heimatbasis auf den Queen Beatrix International Airport von wo ab dem 18.08.1988 der Flugbetrieb mit einer NAMC YS-11 aufgenommen wurde.
Von diesem Flugzeugtyp setzte Air Aruba insgesamt drei Maschinen ein die noch durch zwei Embraer EMB-120 ergänzt wurden.
Mit diesen Maschinen bediente man Ziele zwischen Aruba, Bonaire and Curaçao, aber mit der Einführung von geleasten Boeing B-757 konnte man erstmals Miami und New York Newark ins Streckennetz aufnehmen, aber auch Santa Domingo, Bogotá, St. Maarten, Sao Paolo, Maracaibo, Medellín, Maracaibo, Las Piedras wurden bedient.
In den neunziger Jahren änderte man die Flottenpolitik drastisch und so gelangte ein Mix von verschiedenen Flugzeugtypen zur Air Aruba.
So unter anderen Boeing B-727, B-737 und B-767 sowie Douglas DC-9, McDonnell Douglas MD-83, und MD-88.
Nun konnte man das Streckennetz auf Amsterdam, Köln, Houston, Philadelphia und Baltimore ausweiten.
Da Air Aruba jedoch vorwiegend Verluste einflog entschloss sich die Regierung zum Verkauf der Gesellschaft.
Einen Käufer fand man am 27.10.1998 in der venezolanischen Aserca die für Air Aruba insgesamt fünf MD-90 leaste.
Weiterhin wurde das Strecknetz umgestellt und Partnergesellschaften gesucht.
Missmanagement und daraus resultierende finanzielle Verluste war wohl letztendlich der ausschlaggebende Punkt, als Air Aruba am 23.10.2000 den Flugbetrieb einzustellen musste.