På Finansloven i 1995 bevilger Folketinget 444 mio. kr. (1999-priser) til opgradering af det nuværende  flyvekontrolsystem og nye simulatorer til uddannelse af flyveledere. Samme år tilslutter Danmark sig den europæiske Eurocontrol organisation. Dermed går Danmark med i den klub af 37 lande, som arbejder for harmonisering og integrerede lufttrafikstyringssystemer. Det betyder, at Statens Luftfartsvæsen (SLV), hvortil Naviair hørte indtil udskillelsen i 2001, går fra et nationalt perspektiv til et europæisk perspektiv – politisk, organisatorisk, medarbejdermæssigt og ikke mindst teknisk.

Det får stor betydning for valget af fremtidens teknologi. For med deltagelsen i Eurocontrol har Danmark pligt til at arbejde for, at fremtidens trafikkontrolsystemer kan tale sammen, at de kan integreres. Integration er forudsætningen for tættere samarbejde eller fusion af Europas flyvekontroltjenester. Alle ideer om at bygge videre på det eksisterende flyvekontrolsystem bliver skrinlagt i 1996. Det eksisterende system skal nu kun opgraderes, så det kan klare den stigende flytrafik, i perioden indtil et helt nyt, standardiseret system står klar. Det bliver derfor besluttet, at det gamle system skal have forlænget sin levetid – og så skal Naviair satse på et helt nyt, moderne og internationalt standardiseret system. Københavns Lufthavn har midt i 1990’erne planer om at udvide lufthavnen for at kunne håndtere den stigende trafik. Derfor skal der bygges et nyt kontroltårn med en anden placering end den nuværende, for at sikre at flyvelederne har fuldt udsyn over standpladser og baner i den udvidede lufthavn. Det nye tårn bliver del af projektet med et helt nyt flyvekontrolsystem i Danmark. Med udgangen af årtiet ligger hele projektet beskrevet og klar til at bygge. I 1999 revurderes og ændres projektet og Folketinget bevilger yderligere 514 mio. kr. (1999-priser) til et helt nyt flyvekontrolsystem inkl. ny bygning til kontrolcentral og nyt tårn på Københavns Lufthavn. I slutningen af 1990’erne moderniseres det eksisterende flyvekontrolsystem, mens Naviair samtidig beskriver kravene til fremtidens system og begynder at kikke sig om efter leverandører. I Sverige og i Irland – blandt mange andre europæiske lande – er man i gang med en tilsvarende proces. Det nye flyvekontrolsystem kræver helt nyt udstyr og ikke mindst helt nye computerprogrammer – og da det viser sig at være dyrt og fører til forsinkelser at udvikle de nye systemer, vælger Naviair at holde lidt igen med investeringerne og valget af hovedleverandør. Naviair vurderer, efter gennemgang af tilbuddene, at den franske producent Thales har givet det mest fordelagtige tilbud på det nye danske system. De leverer også til svenskerne. Da projektet er kommet så godt i gang i Sverige, at svenskerne kan se afslutningen på det, indgår Naviair kontrakt med Thales. Det er i 2002. Undervejs justeres projektet og udvides flere gange. I 2001 beslutter Forsvaret, at de ikke vil benytte muligheden for at være fælles med Naviair om flyvekontroludstyr og vælger i stedet at få sit eget system. Det betyder, at bevillingen til Naviairs del af projektet bliver forøget med 46 mio. kr. på finansloven 2002. I 2001 overtager Naviair forpligtelsen for udstyret til kontroltårnet i Billund, hvilket heller ikke var en del af den oprindelige aftale. Den sidste finanslovsbevilling er fra 2006, hvor der bevilges 123 mio. kr. (2005-priser) primært på grund af, at det oprindelige budget til nyt tårn i Københavns Lufthavn var utilstrækkeligt. Dermed løber bevillingen til Danmarks nye flyvekontrolsystem op i 1.228,4 mio. kr. (2005-priser).