La première unité de la NVAF était le régiment de transport n°919 créé le 1 mai 1959 et disposant d’appareils modèles An-2, Li-2, Il-14. Le Régiment d’entrainement n°910 fut mis en place avec des Yak-18 d'entrainement. En 1963, les forces, aérienne et de défense aérienne, furent regroupées.
Le premier appareil de combat nord-vietnamien était un T-28 Trojan d’entrainement récupéré suite à la désertion de son pilote de la Royal Lao Air Force. Il fut utilisé dès 1964 comme avion de combat pour mission de nuit, le T-28 fut le premier appareil nord-vietnamien à abattre un avion U.S, un C-123, le 15 Février 1964.
La NVAF reçut son premier avion de combat à réaction, le MiG-17 en février 1964, mais les appareils restèrent stationnés sur des bases aériennes en Chine durant toute la formation de leur pilotes. Le 3 février 1964, un premier régiment n° 921, "escadron étoile rouge" était formé, il débarqua avec ses MIG-17 le 6 aout au Nord Vietnam.
Une deuxième vague de pilotes rentrés en 1965 permit d’inaugurer une deuxième unité le 7 septembre 64, le régiment de combat n° 923 "escadron Yen ".
En Mai 1965, la compagnie de bombardier N°16 fut activée avec des bombardiers bi-moteurs Il-28. Seul un Il-28 opéra une sortie de combat en 1972 contre les forces royales laotiennes.
Les MiG-21 arrivés d'URSS en 1966 furent attribués aux plus anciennes unités nord-vietnamiennes, le 921ème régiment qui était équipé jusqu'à lors de MiG-17. Comme le 923ème était récent et moins expérimenté il continua à opérer sur MiG-17 jusqu'à l'arrivée de la version chinoise des MiG-19, le Shenyang J-6 en 1969. Le Nord-Vietnam créa alors en 1969 également une unité dédiée au MiG-19,le 925ème. Le 24 mars 1967, les régiments n° 921, 923 et 919 furent incorporés au sein de la 371ème Division aérienne. Le 3 février 1972, le quatrième et dernier régiment créé durant le conflit vu le jour, le 927ème régiment, "Lam Son",équipé du MiG-21PFM (Type 94).