L’occupation de l’Algérie par la France, à partir de 1830, coïncide, à quelques années près, avec l’avènement de la marine à vapeur, qui vient progressivement remplacer la marine à voile, et permet d’établir des liaisons régulières en mer Méditerranée.
Ce sont des bateaux de type « aviso », appartenant à la Marine Royale, basée à Toulon, qui assurent des liaisons entre Toulon, les îles Baléares sur lesquelles est constituée une base-escale, et Alger, pour le transport de troupes, de matériels et le ravitaillement. Il fallait à l’époque 60 heures pour aller de Toulon à Alger.
Ainsi, l’acheminement du courrier, vers ou en provenance de la France, est pris en charge par l’Armée. Une fois arrivés à Toulon, les courriers sont acheminés vers leur destination, d’où la présence d’un cachet « Toulon » sur presque tous.
A partir de 1833, le service est assuré par des liaisons maritimes régulières entre Toulon et Alger, liaisons latérales d’Alger vers l’est et d’Alger vers l’ouest, le long des côtes, le tout sous privilège de l’État jusqu’en 1841.
A cause d’épidémies de choléra, à leur arrivée à Toulon les correspondances étaient soumises à « purification ». Cette purification était effectuée au Lazaret de la rade de Toulon par immersion des lettres dans un liquide, ou par fumigation au travers d’incisions pratiquées dans la lettre.
En 1841, des compagnies privées de navigation établissent des lignes régulières, qui relient Marseille et Alger en 48 heures. Sur ces bateaux se trouve une véritable boîte aux lettres où déposer les courriers, appelée boîte mobile, d’où la création de cachets spéciaux « bateaux à vapeur ».
A partir de 1848, il est même possible, sur les bateaux de ces compagnies privées, de poster un courrier à bord, soit au départ, soit en cours de traversée : de Marseille ou Sète vers Alger, Oran ou Stora (Philippeville).