Ces dispositions ont été reprises et complétées par un arrêté en date du 19 février 1958 qui porte création des agences postales militaires. Il énonce notamment :

Article 1er : des agences postales peuvent être installées sur les territoires métropolitains et des départements d’outre-mer dans des camps et bases des formations des Armées de Terre, de Mer et de l’Air d’importance suffisante.

Article 4 : les dispositions de l’arrêté du 10 octobre 1955 portant création des agences postales de l’Air sont annulées.

Une instruction du même jour fixe précisément la réglementation de ces agences postales militaires :

 une agence postale militaire peut être installée dans un camp ou une base militaire éloigné de tout bureau de poste et dont l’effectif réglementaire atteint le chiffre de 1.000 hommes,

 l’agence porte le nom de la désignation du bureau d’attache suivi du mot « Air »,

 l’agence postale est gérée par un sous-officier assermenté, titulaire de la « Mention d’aptitude aux fonctions postales », mention délivrée après un stage d’une durée de 6 semaines dans un bureau de poste,

 les opérations effectuées par l’agence postale militaire sont centralisées et contrôlées par la recette des postes désignée comme bureau d’attache.

La première agence postale desservant une base aérienne fut l’agence « Toulouse-Fracazal Air » qui fut ouverte le 16 novembre 1956. Toutes les agences postales de l’Air sont situées en France à l’exception de l’agence « Ouakam Air » (Sénégal) desservant la base aérienne 160.

Dans un premier temps la plupart des agences postales de l’Air utilisèrent des timbres à date hexagonaux pointillés à angles fermés de 29 mm de diamètre. Ces oblitérations étaient apposées au moyen de timbres à date en bronze. Certaines agences employèrent 2 types de ces cachets, variant seulement par la taille et la disposition des caractères. Quelques agences reçurent des timbres à date hexagonaux à trait plein.

L’agence postale d’Orléans-Bricy fut la seule à utiliser un timbre à date hexagonal couplé avec 5 lignes ondulées verticales frappées par une machine Daguin.

A la fin de l’année 1962 commencent à apparaître les premiers timbres à date hexagonaux à angles ouverts, frappés à l’aide de timbres à date en plastique. La réforme du code postal suscita la création en 1965/66 de nouveaux timbres à date du même type mais mentionnant le code à 2 chiffres du département.

Dans les agences dont le trafic était le plus important furent également mises en service, en 1962, les premières oblitérations mécaniques SECAP comportant un timbre à date pointillé à angles ouverts, de 24 mm de diamètre, et 5 lignes ondulées.

En 1966/67 apparurent les premiers timbres à date manuels circulaires de 27 mm de diamètre et les premières oblitérations mécaniques SECAP circulaires de 24 mm de diamètre accompagnées de 5 lignes ondulées disposées à gauche du timbre à date. A partir de 1970/71, les lignes ondulées ont été placées à droite du timbre à date.

Certaines agences ont mis en service des flammes temporaires illustrées. Des bureaux temporaires rattachés à ces agences ont utilisés des timbres à date grand format illustrés, notamment lors de meetings aériens et de journées portes ouvertes.

Certaines agences importantes ont été dotées de machine à affranchir de guichet ou de systèmes d’impression de guichet. Elles sont parfois bureau de rattachement de machines à affranchir d’unités de l’armée de l’Air.