L'histoire de la marine algérienne, est liée à la façade méditerranéenne qui a influencé l'histoire du pays. vignette|La côte algérienne en 1774 d'après le géographe français Joseph Bernard de Chabert.
Les origines de la navigation en Afrique du Nord Les ports naturels et les défenses des villes côtières, la proximité de l'eau douce et l'arrière-pays riche et productif attirèrent les Romains, Vandales, Byzantins et Arabes. Les premières traces d'une activité maritime : l'antiquité numide et punique vignette|240x240px|Navire numide sur une stèle carthaginoise (Musée national de Carthage).
Si la navigation a pu être pratiquée par les premiers Numides pour la pêche sur de petites embarcations, c'est à l'influence punique que les Numides doivent l'apport des sciences de la navigation et de la construction de navires pour la haute mer. Les Phéniciens, puis les Carthaginois implantent et maintiennent une série de points côtiers qui leur permettent de commercer par cabotage. Les côtes algériennes ont mauvaise réputation depuis l'Antiquité pour leur aspect difficile et escarpé ; hormis certains mouillages reconnus comme sûrs et propices au stationnement de navires (Mers el-Kébir qui passe pour être le meilleur, Alger, Béjaïa ...) . C'est dans ce cadre que la ville d'Alger, alors dénommée Ikosim est fondée vers le Elle est intégrée au dispositif des échelles puniques : une série de ports, qui constituent des points relais espacés de le long des côtes nord-africaines.
La Numidie, puissance terrestre, est très peu portée vers la mer et l'on dispose de très peu d'informations sur les activités maritimes numides (contrairement à celles de leur voisin de Carthage). Une chronique rapporte, sous le règne de Massinissa, qu'une flotte numide avec à sa tête un commandant, dérobe des défenses d’éléphant d'une grande valeur dans le temple de Junon sur les côtes de Malte.
Des Romains à la conquête arabe vignette|droite|La méditerranée en 146 av. J.-C..
L'expansion carthaginoise et romaine provoqua des conflits, et les hostilités éclatèrent lors des guerres puniques (264 av. J.-C. à 146 av. J.-C.). Les tribus numides soutinrent différents camps dans cette guerre. Le roi Massinissa, s'allia à Rome et prit part à la bataille de Zama durant la deuxième guerre punique survenu en 202 av. J.-C., qui mit fin à la guerre avec la défaite de Carthage. La fin de la troisième guerre punique (149 -146 ) et le pillage de Carthage marquèrent le début de la présence romaine en Afrique du Nord. Avec le soutien des Romains, Massinissa établit son propre royaume de Numidie, à l'ouest de Carthage, avec Cirta (Constantine) comme capitale. La Numidie s'épanouit sous son règne et celui de son fils Micipsa. Lorsque Bocchus II roi de Maurétanie mourut en 33 av. J.-C., il légua son royaume à Rome. Néanmoins, l'empereur romain Auguste choisit de ne pas annexer le pays, et la Maurétanie devint un royaume autonome mais qui restera le vassal économique, politique et militaire de Rome. Il nomma Juba II sur ce royaume client dont sa principale mission est de protéger la frontière occidentale de Rome et de contrôler les côtes. La Maurétanie fut divisée après la mort de Juba II, c'est ainsi qu'à vu naître la Maurétanie césarienne (actuelle Cherchell) à sa tête Ptolémée de Maurétanie. Des villes côtières furent fondées comme Tipasa, Caesarea, Hippo Regius et Icosium, dont les ports constituaient le noyau central pour le contrôle des côtes. Rome exerça sur la méditerranée, artère vitale de son empire, une maîtrise absolue.
vignette|droite|Carte du royaume des Vandales et des Alains en 526. Les Vandales arrivent en Maurétanie en 429 et rentrent à Hippone en 430. Ils ont assuré leur autorité sur toutes les villes du nord de l'Algérie pendant un siècle. Le roi Genséric écrase les armées conjointes des empires romains d'Orient et d'Occident, qui sont envoyées contre lui. En 435, il conclut un traité avec les Romains, en vertu duquel, les Vandales conservent la province romaine de Maurétanie césarienne et une partie de la Numidie, étendue jusqu’à Hippone et Calama, en tant que peuple fédéré de Rome. Forts de leur domination des villes côtières, et d'une complicité avec les Berbères de l'intérieur du pays, les Vandales prennent en 439 Carthage, réserve de la flotte romaine d'Occident . Depuis leur port de Carthage, les Vandales lançaient leur flotte et contrôlaient la Méditerranée. La marine de Genséric pillait tous les navires qui croisaient son chemin et faisait des raids sur les côtes. Les tentatives des Romains pour chasser Genséric et son peuple d'Afrique du Nord n'aboutirent à rien, et ainsi en 442, les Romains reconnurent le Royaume Vandale comme un pouvoir politique légitime, et un traité fut signé entre Genséric et Valentinien III. En 455, Genséric lance une attaque contre l'Italie avec sa flotte, et arriva à Ostie et marcha sur Rome. Les Romains reconnurent que leur force militaire était insignifiante par rapport à celle des Vandales. En 460, les Romains rassemblèrent leurs forces et lancèrent une attaque contre les Vandales, mais Genséric s'emparera de la majeure partie de la flotte romaine. En 468, les deux parties orientale et occidentale de l'Empire s'unirent contre les Vandales et envoyèrent contre eux l'ensemble de leur flotte. Genséric surprit les Romains et les vainquit, détruisant de leurs navires et capturant les autres. Rome fut obligée de demander la paix. Après la mort de Genséric en 478, le royaume vandale commença à décliner. Les Maures se soulevèrent contre le royaume vandale du nord et défirent les forces d'Hildéric vers la fin de son règne. Sa défaite devant les Maures pousse son cousin Gélimer à le déposer, et il devint roi des vandales en 530. Trois ans plus tard il fut battu par les Byzantins commandés par le général Bélisaire. Le royaume vandale d'Afrique du Nord était tombé, et avec lui les Vandales furent dispersés.
vignette|droite|L'Empire byzantin vers l'an 600. Les Byzantins avaient un problème avec les Berbères et les africains romanisés. Ces derniers ont été persécutés par les Vandales et ça va continuer sous l'autorité byzantine.Les rebelles berbères sont définitivement abattus en 548. De 550 à 554, un contingent byzantin conquiert une large bande de terre au sud-est de l'Espagne. La Méditerranée est redevenue une mer romaine, même si l'ancien Empire n'existe plus. Après une accalmie durant le règne de Justinien Ier, le déclin de l'Empire s'accentue sous ses successeurs. Les reconquêtes d'Héraclius sont sans lendemain, et les territoires recouvrés vont être conquis en une décennie par les Arabes musulmans, dont l'expansion fulgurante débute quelques années après la mort du prophète Mahomet en 632. La conquête musulmane du Maghreb va se faire de 647 à 709. Toutes les batailles étaient terrestres. L'utilisation des flottes marines était insignifiante. vignette|gauche|Cate des premières conquêtes musulmanes de 630 à 820
L'impulsion ziride et hammadide : un nouveau rôle en Méditerranée Le Maghreb central va connaître, au cours du , l’avènement d'une dynastie berbère sanhadja, les Zirides dont la capitale est Achir (une ville de l'arrière-pays) avant de migrer vers Kairouan pour remplir le rôle d'émir au service des califes Fatimides. Les Zirides fondent, sur la modeste bourgade qu'est devenue Icosium, Alger (Al Jaza'ir) qui devient rapidement un port et une ville commerçante de premier plan. La ville possède notamment une flotte marchande qui établit des liaisons avec Al-Andalus et la Méditerranée occidentale. Les Zirides héritent d'une partie de la flotte fatimide au (alors reconnue comme dynastie califale) ; cette flotte est basée à Mahdiya (Tunisie) et les Zirides occupés par des problèmes internes délaissent cette flotte dans un premier temps. Ils implantent cependant des chantiers navals en Tunisie et à Béjaïa (la Kabylie, arrière-pays de cette ville fournit les quantités de bois nécessaire à la construction et l'entretien de la flotte). Les Zirides et leurs successeurs Hammadides continueront à envoyer régulièrement des renforts navals, jusqu'aux années 1070, aux émirs kalbites de Sicile, face à l'implantation et l'avancée des Normands.
Une branche des Zirides, les Hammadides, fait sécession et s'érige en dynastie régnante sur le Maghreb central au . Ils développent la ville de Béjaïa jusqu'à en faire un port méditerranéen de premier plan au . La position littorale de leur nouvelle capitale les tourne vers la mer. L'arrière-pays leur fournit les ressources nécessaires pour le maintien d'une flotte importante, El-Idrîsî () décrit la ville :
.
La ville de Béjaïa devient la base hammadide pour les expéditions au pays des Roum (Italie médiévale et Sicile). La flotte hammadide est également une flotte marchande et de corsaires. Cependant elle doit faire face à la concurrence des marchands italiens, notamment génois. Le long de ce littoral méditerranéen se développent par ailleurs des ports comme Bône, Oran et Alger dominés par des marchands d'origine andalouse. Les Hammadides tournent leurs premières expéditions contre Mahdiya (siège politique de leur cousins et rivaux Zirides). Face au déclin maritime ziride, la flotte hammadide ne tarde pas à sillonner toute la Méditerranée. Mais elle doit faire face à la puissance émergente des Normands de Sicile. La bataille de Mahdia (1054) voit l’échec de la flotte hammadide face à une flotte sicilienne normande de venus délivrer les Zirides de la tutelle hammadide. Les Normands évincent ensuite les Hammadides de certaines positions méditerranéennes comme Djerba en 1135.
L'accroissement de l'activité maritime influence la politique locale durant toute la période médiévale. Les ports prennent une grande importance dans la vie politique, économique, sociale et culturelle du Maghreb. À partir du , ces villes deviennent un enjeu pour les pouvoirs en place et nécessitent une présence accrue et renforcée. Cette mutation politique est décrite dans l'ḥisba du sévillan Ibn ‘Abdūn au . La citadelle, est traditionnellement le siège du gouvernement et se trouve située dans la mesure du possible en hauteur, des éléments plus légers protègent le bassin du port. À Béjaïa, deux édifices au contact de la mer visent à défendre le bassin (l'actuelle Casbah et le bordj AbdelKader) en plus de bénéficier d'un abri dans les remparts pour les navires.
Les Almohades et les autres dynasties postérieures prolongent cette politique maritime de leur prédécesseur. Le port de Honaïne, débouché de Tlemcen, connaît un aménagement similaire avec des fortifications, une casbah (citadelle) et différents éléments de défense, notamment un arsenal, des tours (bordj) et des remparts. Deux fonctions chargées des affaires maritimes sont affiliées aux administrations des gouverneurs ou aux sultans : le « chef de la mer » qā’id al-baḥr ou « chef de la flotte » qā’id al-usṭūl et un chef des douanes. La marine prend un rôle de premier plan au Moyen Âge car au centre des relations avec les nations chrétiennes, tant commerciales que conflictuelles. Vers la fin du , un certain Muhammad b. Abī Mahdī, amiral (qā’id al-usṭul) de Béjaïa, est tuteur de l’émir de la ville (dissident Hafside), encore mineur, et gouverneur de fait de la ville. Il développe à grande échelle le corso (piraterie) contre les nations chrétiennes et prévoit des dispositifs de défense de la ville.
Les Almohades héritent de la flotte des Zirides et Hammadides qu'ils ont conquis ; ainsi ils sont à la tête d'une des plus grandes flottes du bassin méditerranéen. Béjaïa devient un des principaux arsenaux de leur dispositif maritime en Méditerranée. Abd el Mumin, premier calife almohade, met en place un gouverneur issu de sa propre famille, témoignant de l'importance stratégique de la ville.
La régence d'Alger : une puissance maritime de premier plan en Méditerranée vignette|Le chébec du marin espagnol Dom Antoine Barcelo (au centre) face à deux galiotes de la régence d'Alger. (1738)|280x280px