La situation empirant et les effectifs à desservir atteignant 160.000 hommes en septembre 1955 (au lieu de 25.000 initialement), il fut décidé le 9 novembre 1955 d’établir un véritable service de la Poste aux armées en Algérie. Le 1er janvier 1956, le service se composait d’une direction, d’un bureau frontière (le bureau Q à Alger) et de 5 bureaux postaux militaires avec 8 annexes.
Les effectifs de la Poste aux armées en Algérie furent portés à 835 personnes le 30 juin 1956 et le nombre des bureaux postaux militaires à 25 avec 29 annexes.

En 1961, 28 bureaux postaux militaires et 46 annexes fonctionnaient en Algérie. Les numéros des bureaux furent, pour la plupart, pris dans les séries 400, 500 et 600.
Les militaires français étaient rattachés aux secteurs postaux des séries 86000, 87000 et 88000. Ils bénéficiaient de la franchise pour le courrier qu’ils envoyaient et recevaient.
Les bureaux postaux militaires en Algérie oblitéraient les correspondances à l’aide de timbres à date manuels (différents modèles) ou oblitérations mécaniques type KLUSSENDORF puis SECAP (avec lignes ondulées ou texte) avec couronnes « POSTE AUX ARMEES A.F.N. » (Afrique française du Nord).
Le règlement de la Poste aux armées interdisant depuis décembre 1953 l’usage des timbres à date à numéros, même sur les courriers recommandés, ceux-ci n’étaient apposés que sur des récépissés et sur des documents administratifs et comptables internes à la Poste aux armées.