Après l'indépendance en 1962, la marine nationale algérienne, sous l'impulsion du colonel Mohamed Benmoussat (1962-1978), commença à se développer avec l'acquisition de différentes unités navales en Italie tels les Bagliétto et les Mangusta pour les gardes-côtes, puis l'acquisition d'unités plus grosses et mieux armées en URSS, notamment les OSA I et II, les poseurs de mines T-34 ainsi que des vedettes de surveillance.
En 1969, le port militaire de Mers El Kebir fut récupéré, donnant à l'Algérie l'opportunité de développer des chantiers navals. La marine algérienne se développa considérablement depuis cette date et durant les années 1980. Elle réceptionna en tout :
deux sous-marins classiques de la classe Roméo de 1982/1983;
trois frégates anti sous-marins de la classe Koni entre 1980 et 1984, armées de missiles surface-air Gecko et de quatre canons de 76 mm;
trois corvettes lance-missiles entre 1980 et 1983, équipées toutes de trois missiles surface-surface et de 20 missiles Gecko.
Plusieurs vedettes rapides de conception britannique de la classe El-Kebir. Les deux premières unités furent produites en Grande Bretagne et les autres au chantier naval de Mers El-Kebir.
La marine dispose aussi de 3 navires de débarquement, deux de conception anglaise de la classe Kalaat Beni Hamed et un polnochny de conception polonaise.
Les deux dernières unités majeures à être importées avant la chute de Berlin furent les deux sous-marins de la classe Kilo en 1987 et en 1988.
Durant la crise des années 1990, les experts occidentaux disaient que la marine ne pouvait pas opérer la totalité de ses navires, notamment les OSA, les Nanuchka et les Koni. Mais c'était sans compter sur les prouesses techniques qu'avaient réalisées les ingénieurs de Mers El Kebir. Dans les chantiers navals, les pièces de rechange étaient fabriquées pour maintenir la flotte opérationnelle.
En 1996, la marine nationale est passée officiellement du statut de marine de littoral à celle de marine de haute mer et ce après la décision d'entamer un vaste programme de modernisation. Mentionnant en passant, que les Français ont refusé de fournir des missiles Exocet sous prétexte de ne pas déséquilibrer l'équilibre des forces entre le Maroc et l'Algérie. Ainsi, les SS-N-2 Styx furent échangés avec des systèmes beaucoup plus modernes comme les SS-N-25. Une des 3 Koni fut aussi équipée de torpilles, les OSA-II reçurent toutes des SS-N-2C, avec un rayon d'action plus grand.
Mais le plus important développement fut la construction de 3 corvettes de la Classe Djebel Chenoua. Équipées de missiles chinois C-802 de 120 km de portée, de systèmes de combat anti sous-marins et de missiles anti-aériens qui représentent les principales unités de combat de la marine. À l'avenir, d'autres unités de ce type seront amenées à remplacer les vieilles Nanuchka d"origine soviétique.
Le but avoué de la marine fut atteint avec une auto-suffisance totale en matière d'acquisition de nouvelles unités de combat. Le dernier à être importé sera le futur navire amiral de la marine. actuellement en construction en Chine, ce bâtiment aura une longueur totale de plus de 120 m pour un poids supérieur à5000 tonnes. Il aura des capacités de combat anti-navire, ant-sou marins et anti aériennes et aura aussi la capacité de transporter plusieurs hélicoptères.
Aujourd'hui, la marine est forte de 9000 hommes et femmes, tous contractuels. La côte algérienne est divisée en trois façades opérationnelles:
Façade Est: dirigée à partir de la base de la ville de Annaba;
Façade Centre: dirigée par l'amirauté d'Alger et est le centre de commandement des forces navales;
Façade Ouest: dirigée à partir du port de Mers El-Kebir. Cette façade est la plus imposante de toutes.
Les patrouilles aériennes maritimes et la couverture aérienne est assurés par la défense aérienne du territoire (DAT). Les missions de soutien sont assurées par les SU-24Bis/MK et les missions de reconnaissances par les Fokker 27 et les B-200T. Les hélicoptères KA-32 utilisés pour les missions navales sont sous l'autorité de la AAF et sont utilisée pour les mission SAR (Search And Rescure) ou pour la détection de sous marins.
Pour les entraînements aériens, les avions de l'AAF font des manœuvres annuelles majeures avec la marine, alors que des Mirach-100 sont utilisés pour les missiles surfac-air des unités navales. La défense côtière quant à elle utilise des batteries mobiles de SSC-3 Styxx qui est la version su sol du SS-N-2C, ainsi que des batteries mobiles de SS-N-25 Uran, version navale du KH-35.
En plus, des changements dans les systèmes d'armes ne peuvent qu'ajouter à la force de la marine, notamment l'introduction de missiles modernes, SS-N-25 et C-802 anti-navire au lieu des SS-N-2C, et l'installation de missiles air-air SA-N-10 au lieu des vieux SA-N-4. La marine dispose aussi de systèmes IFF permettant de différencier les matériels amis et ennemis que ce soit des navires ou des avions de combat.
L'académie des forces navales de Tamenfoust forme les principaux membre de la marine dans les domaines de la navigation et de l'utilisation des différents types d'armements. Elle dispose d'un simulateur de navigation qui permet aux futurs commandants de bord d'avoir une idée bien précise de la navigation et sur l'utilisation des moyens de communications et de combat dans les différents cas imposables par ordinateurs.
Des manœuvres dans des conditions de combat réelles. Les deux sous-marins de la classe kilo donnent aussi à l'Algérie un avantage immense dans la rive sud de la méditerranée, surtout depuis leur modernisationen Russie et leur nouvelle couverture installée au début de l'année 2001, qui est un plastique qui diminue leur signature radar et les rend pratiquement indétéctables.
Autres mission de routine, les missions SAR qui sont en fait de la recherche et le sauvetage en mer, Chaque année, plus de 300 clandestins d'origine sub-saharienne ou marocaine sont secourus par les navires de la marine nationale. Ces clandestins sont surtout victime de pannes des moteurs de leurs embarcations et qui sont dévié de leur but d'orgine, les côtes espagnoles.
D'autres missions de ce type sont effectuées sur la côtes est du pays. Ces dernières concernent les clandestins sub-sahariens qui ont pour point de départ les côtes libyennes. Très souvent, la marine tunisienne sollicite l'aide de la marine algérienne pour la recherche et le sauvetage de clandestins se dirigeant essentiellement vers Malte et les côtes italiennes.
La lutte anti-drogue et anti-terroriste figure aussi dans les missions de la marine, surtout après la dispersion des éléments d'Al-Qaida et la prévention d'attaques contre les pétroliers et les navires civils.
Ces cinq dernières années ont a vu un rapprochement important avec l'OTAN, notamment avec l'organisation des manœuvres aéronavales avec la marine américaine et l'utilisation de sous marins nucléaires, destroyers, corvettes, vedettes, frégates, avion P-3, hélicoptères KA-32 et engagement de SU-24. En septembre 2003, la marine algérienne participa pour la première fois à des manœuvres conjointes entre les pays de l'OTAN et ceux de l'Europe de l'Est.