En 1964, l’Algérie acquit ses premiers avions offensifs : 50 MiG-15Bis et MiG-17F en plus de 14 bombardiers tactiques IL-28. Mais le projet ne s’arrêta pas là, l’Algérie acquit en plus 6 autres avions de transport Il-14, 1 Il-18 pour le gouvernement et le super transporteur russe de l’époque l’An-12 qui furent livrés avec à leurs bords des tonnes d’armes et de munitions pour l’armée de Terre. L’URSS modernisa également la base aérienne stratégique de Boufarik qui fut utilisée pour le soutien logistique de la FAA.
En 1965, un changement à la tête de l’État amena Houari Boumédiène au pouvoir. Ce dernier commença par changer le nom officiel de la force aérienne algérienne en Al Quwwat Al-Jawwiya Al-Jaza'eriya (QJJ). il mit en place un ambitieux programme de modernisation et de formation et renforça également la coopération avec l’Union soviétique dans le domaine de l’armement, c’est ainsi que les premiers avions de combat modernes firent leur apparition au sein de l’AAF. L’Algérie acquit donc deux escadrons de chasseurs bombardiers MiG-17F, 20 autres hélicoptères MI-4 pour le transport, les missions d’attaque au sol et pour les missions de reconnaissance d’artillerie ainsi que 16 autres bombardiers IL-28. Mais l’événement qui provoqua une grande polémique avec le Maroc fut l’arrivée de 6 avions supersoniques MiG-21F-13.
Au début de l’année 1967, 31 nouveaux MiG-21 furent livrés à l’AAF, qui les divisa en deux escadrons d’interception et de chasse.
Les premiers combats des pilotes algériens commencèrent en 1967 avec la guerre des Six Jours, quand 2 escadrons de MiG-17, un de MiG-21 et un autre d’IL-28 furent engagés auprès de la coalition arabe. Avec près de 100 appareils l’Algérie alignait la deuxième force aérienne sur le front égyptien. Les MiG-17 étaient pilotés par des aviateurs algériens tandis que les MiG-21 par des aviateurs égyptiens qui étaient censés avoir plus d’expérience dans l’utilisation de ce nouvel avion. Mais à leur arrivée, les 6 premiers MiG-21 se posèrent sur la base aérienne d’AL-ARICH dans la péninsule du Sinaï qui entre temps était passée sous le contrôle des forces Israéliennes de Défense (IDF). Les 6 avions et leurs pilotes égyptiens furent capturés. Quatre des MiG-21 furent remis aux États-Unis afin de les tester et découvrir ainsi d’éventuelles faiblesses de cet appareil qui les faisait tant souffrir durant la guerre du Vietnam. Certaines sources rapportent par ailleurs que des MiG-17 ont participé à des bombardements contre des troupes israéliennes au Sinaï suite à la débâcle des troupes arabes.
Suite a la defaite face a Israel, l’Algérie décida d’intensifier l’entraînement de ses pilotes avec l’acquisition d’un lot de 28 avions d’entraînement CM-170 Fouga Magister et 5 hélicoptères SA-330 Puma. Ces CM-170 appartenaient à l’origine à la Luftwaffe de l’Allemagne fédérale, ils furent transférés en France pour être rénovés et modernisés et enfin livrés à l’Algérie.
Au début de l’année 1971, l’AAF comptait près de 200 appareils avec comme avion principal le légendaire MiG-21 qui composait près de 40 % de la flotte, les MiG-15 et MiG-17 ont prouvé qu’ils ne faisaient plus le poids face à des avions tels que le F-4 Phantom.
Les premiers chasseurs bombardiers Su-7BMK (avion qui à l’époque était à la pointe de la technologie) ont fait leur apparition avec pour but de remplacer les MiG-17F, donnant à l’Algérie un avantage militaire qui faisait d’elle la seule nation ayant acquis ce type d’appareil dans le bassin méditerranéen.
En 1973, deuxième engagement direct de l’Algérie dans le conflit israélo-arabe. Elle fut encore une fois la deuxième puissance militaire sur le front égyptien et sa force était composée d’un escadron de bombardiers tactiques Su-7 escorté par un escadron de chasse MiG-21. Un troisième escadron équipé de MiG-17 fut envoyé pour des missions de soutien.
Le conflit du sahara entre Espagne et Maroc et qui s'acheva par la decolonisation pure et simple sous la pression de la diplomatie Marocaine et l'organisation de la marche verte n'a pas plu aux Algeriens qui cherchent une issue sur l'ocean atlantique et s'accomode mal avec un Maroc enfin presque dans ses frontières naturelles. L'Algerie ouvre son sol aux opposants sahraouis et separatistes de tout bord, les entraina et les arma, le Maroc de son coté remet le tracé ders frontières sur la table et rejette le fait accompli par l'ancien colon .. le Maroc reclame Tindouf et Bechar, de plus, le royaume n'a toujours pas encore oublié la coalition algero-egymtienne des années 60 dans l'espace Hassi baida..
Resultat, l'algerie vacille dans l'incertitude et se lance dans l'achat massive d'armement...
Au début de 1978, l’AAF était composée de 5 000 hommes et équipée de 230 avions de combat. La flotte était constituée de 120 MiG-21MF, un escadron de chasseur bombardier équipé de 28 SU-7BMK, un escadron d’attaque équipé de MiG-17, un escadron de bombardiers tactiques équipé de 24 IL-28 et un escadron de 20 CM-170 et 20 MiG-15 pour l’entraînement.
Ce n’est que vers la fin de 1978 que le premier lot de 50 MiG-23 à géométrie variable fut acquis, mais l’avion qui donna à l’Algérie un avantage décisif dans la région en termes militaire et politique était le Mikoyan-Gourevitch MiG-25M Foxbat. Seuls 5 pays furent approuvés à l'époque par Moscou pour recevoir cet avion aux performances exceptionnelles et qui demeure toujours en service au sein de l'AAF, qui l'emploie notamment dans le domaine de la reconnaissance aérienne
La même année, les systèmes d’entraînement furent restructurés et les premiers avions d’entraînement El Joumhouria furent remplacés par des T-34C acquis aux États-Unis.
En 1981,L’Amérique offrit 6 Hercules C-130H (en recompense a leur mediation dans l'affaire des l'affaire des otages en Iran), principal avion de transport tactique des États-Unis à cette époque-là et qui fut utilisé en tandem avec son équivalent soviétique l’AN-12. D’autres C-130H et C-130H-30 furent acquis par l’Algérie dans les années 1980.
Durant cette même période, la flotte de combat fut largement modernisée, d’autres MiG-23 et MiG-25 furent acquis et l’immense flotte de MiG-21F fut échangée avec 120 MiG-21MF/Bis plus modernes. Il était clair que l’Algérie cherchait à moderniser davantage ses capacités d’entraînement, plusieurs compagnies proposèrent leurs avions d’entraînement tels que l’Alpha Jet franco-allemand et le Hawk Britannique, mais c’est le L-39 Tchécoslovaque qui fut choisi avec une acquisition de 39 appareils de ce type à partir de 1987.
1990: L’AAF qui comptait près de 500 techniciens russes avant 1990 avait de très grandes difficultés à maintenir sa flotte opérationnelle. Les experts internationaux ne lui donnaient plus qu’un rôle mineur dans la région et disaient qu’elle ne pouvait supporter la maintenance de sa flotte.
Mais malgré ces problèmes l’AAF tint le coup et sa force de dissuasion était toujours là, grâce notamment à ses 13 SU-24MK et 4 SU-24MR acquis 2 ans seulement avant la chute de l’URSS. Sa flotte de MiG-25 fut également d’un apport précieux dans le maintien du rôle de dissuasion au niveau régional. Le transport militaire fut lui aussi modernisé grâce à l’acquisition des IL-76 (avions de transport stratégique), et à une flotte d’hélicoptères Mi-8 et Mi-17 qui furent équipés avec des systèmes de vision nocturne, alors qu’une commande de 30 SA-330 PUMA fut annulée notamment après le crash des deux seuls appareils à avoir été livrés