Au début de 1863, à Paris, trente-cinq bureaux de poste de quartier sont ouverts au public : dix bureaux principaux d'arrondissement, identifiés par une lettre de A à K, trois bureaux secondaires, identifiés par les lettres L (Sénat), M (Corps Législatif) et N (ancienne Maison du Roi), et vingt-deux bureaux supplémentaires, chacun identifié par la lettre du bureau principal auquel il est rattaché, suivie de la lettre S et d'un numéro d'ordre. La suscription des lettres au départ est frappée par un timbre à date, et l'affranchissement est oblitéré par un losange de points, portant tous deux l'identifiant du bureau, par exemple HS3 pour le troisième supplémentaire du bureau principal H.

   En application d'une décision ministérielle du 18 juin 1863, la distinction entre bureau principal, secondaire et supplémentaire est supprimée, et à partir du début du mois de septembre, les trente-cinq bureaux sont classés en une seule série, numérotée de 1 à 35, en fonction de l'importance de leur recette, de la plus importante à la plus faible.

B.M. 65 - juillet 1863, pp.338/339 - extrait

   Sur le timbre à date figure désormais l'adresse du bureau, une étoile chiffrée de 1 à 35 remplaçant le losange de points oblitérant. En octobre 1866, cinq nouveaux bureaux sont ouverts, le bureau 35 de la Salpétrière étant repoussé à la quarantième place de la liste (c'est la fameuse étoile 40 !), avant d'être fermé fin 1866.

   L'utilisation de l'étoile cessera à la fin de mars 1876, la suscription et l'affranchissement étant alors frappés, l'un comme l'autre, par le timbre à date du bureau (instr. n°193 - B.M. 03/1876). Selon J.-C. Delwaulle (F.M. 274), "les bureaux de Paris existant en mars 1876 ont cessé d'utiliser l'étoile et chiffres le 28 mars 1876 (date vue effectivement aux bureaux 2, 4, 7, 14, 22 et 35) ; la première date connue à Paris pour le timbre à date oblitérant sur lettre ordinaire est également le 28 mars 1876 (vu au bureau 29, 7E levée), le 29 mars est rencontré plus fréquemment (vu aux bureaux 2, 9, 15, 16, 17, 19 et 30)."