NAS oppsto i kjølevannet av konkursen i Busy Bee i 1993, og fløy frem til 1. april 2003 på ACMI (Aircraft, Crew, Maintenance, Insurance)-kontrakt for Braathens på et femtitalls daglige ruter på Vestlandet med en flåte på seks 50-seters Fokker 50 (tre tidligere Busy Bee-maskiner LN-BBA/BBB/BBC). Disse flygningene skjedde på BU-flightnummer og med Braathens' callsign. Disse flygningene genererte omtrent en halv million passasjerer i året. NAS har sin administrative base i Oslo, teknisk base i Stavanger og operativ base i Bergen. I 2000 omsatte selskapets ca. 109 millioner kroner, og resultatet før skatt endte på 9,2 millioner. I mai 2000 kjøpte NAS 100% av ambulanseflyselskapet Lufttransport AS som fortsatt vil drive under eget navn. I 2001 fløy NAS hele 16.500 avganger og 500.000 passasjerer for Braathens. Kontrakten med Braathens gikk etter ut i oktober 2003, og har etter SAS' kjøp av Braathens ikke blitt forlenget. Dette, sammen med et press i Norge for å få en konkurrent til SAS/Braathens på norske innenriksruter gjorde at NAS besluttet å starte flygninger på egen kjøl med større fly på stamrutenettet.
Eter at Braathens la ned ruten Trondheim-Kristiansund som NAS fløy for Braathens, fikk NAS i oppdrag å fly fast charter på strekningen for Statoil. Denne ruten ble fløyet med en daglig rundtur, men lagt ned 4. januar 2002. Da Braathens la ned sin rute Stavanger-Newcastle (som tidligere hadde blitt fløyet av NAS) 7. januar 2002, startet NAS flygninger i egen regi på ruten med to daglige avganger. Dette er den første ruten selskapet flyr for egen risiko. Samme dag startet selskapet flygninger for Braathens på ruten Oslo-Molde. Stavanger-Newcastle ble lagt ned i desember 20002, etter sterk konkurranse fra Widerøes og et ønske om å konsentrere seg om lavprisflygningene.
