Naxçıvan Hava Limanı tikintisinə 1974-cü il 31 oktyabrda başlanmış və 1976-cı ildə başa çatmışdır. O vaxt 3-cü dərəcəli təyyarələri (, və onlara oxşar) qəbul etmişdir. Ancaq Bakı şəhərinə reyslər həyata keçirilirdi. Hava limanı 1990-cı illərin ikinci yarısında inkişaf etməyə başladı: Naxçıvan Muxtar Respublikasının Ermənistan tərəfindən blokadaya alınması nəticəsində aviasiya nəqliyyat əlaqəsi üçün yeganə vasitə olmuşdur. Bu səbəbdən, 1992-ci ildə, həmin dövrdə Naxçıvan Muxtar Respublikasının Ali Məclisinin (parlamentin) sədri olan Heydər Əliyev Naxçıvan Hava Limanının uçuş enmə zolağının yenidən qurulması təşəbbüsünü irəli sürdü və bu iş yerli mütəxəssislər cəlb olunmaqla qısa müddət ərzində həyata keçirildi. Uçuş enmə zolağının uzadılması nəticəsində hava limanı tipli təyyarələri qəbul etmək imkanı əldə etdi. 1995-ci ildə Naxçıvanda Tu-134 təyyarəsinin qəzası nəticəsində 52 nəfər həyatını itirmişdir. 2002-2004-cü illər ərzində yeni təyyarə vağzalı tikildi, 2004-cü ilin aprel ayında isə Naxçıvan Hava Limanı Beynəlxalq Hava Limanı statusunu qazandı. 2018-ci ildə Bakı, Gəncə (AZAL) və İstanbul-Atatürk (Türk Hava Yolları) istiqamətlərinə müntəzəm uçuşlar həyata keçirilir.

Hava limanının uçuş-enmə zolağının uzunluğu 3300 metr, örtüyün materialı isə betondandır. Hava limanı iki uçuş-enmə zolağına malikdir.

Yüklərin qəbul edilməsi zamanı yük göndərənin iştirakı və onun üzərində şəxsiyyətini təsdiq edən sənədin olması vacibdir. Yük göndərən yükün göndərilməsi haqqında ərizə blankını doldurur və yük anbarına təhvil verir. Sonra yükün göndərilmə haqqı terminalın kassasına ödənilir. Yüklər hava gəmisindən təhvil alınıb yük anbarına yerləşdirildikdən sonra yük sahibinə yükün gəlməsi haqqında məlumat verilir. Onun yük anbarına gəlməsi, şəxsiyyəti təsdiq edən sənədinin və yük haqqında qaimə sənədinin olması vacibdir.

2021-ci il mayın 10-da Naxçıvan Beynəlxalq Hava Limanında Əlahiddə Ümumqoşun Ordunun hərbi aerodromunun açılışı olub. Hərbi aerodromun tikintisinə 2016-cı ildə başlanmışdı. Aerodromda Mi-24 və Mi-8 helikopterləri, həmçinin Su-25 hücum təyyarəsi yer alır.