Paul, Louis, Brun naît le 5 novembre 1905 à Bellenaves (Allier – 03), fils d’Antoine Brun et de Marie Bidet, son épouse.
Lors du recensement de population de 1906, toute la famille vit au lieu-dit Balady, sous le toit du patriarche, Antoine Brun, né en 1854, « chef de maison, fermier, patron », et de son épouse, Mélanie Défrétière, née en 1856. Ils hébergent quatre de leurs fils, ouvriers agricoles – Paul, né en 1881, Antoine, né le 15 mars 1882, Pierre, né en 1885, Alexandre, né en 1889 – et leur fille Marie, née en 1893, tous à Bellenaves. Ils accueillent également deux brus : Marie (« Maria ») Bidet, née en 1887 à Échassières (03), épouse de Paul, et Marie Bidet, née le 26 novembre 1884 à Coutansouze (03), « servante » en 1901 (16 ans), épouse d’Antoine en juin 1903, avec leurs enfants, Félix, né en 1904, et Paul, Louis.
Paul Brun obtient son certificat d’études primaires.
De 1925 à 1927, il effectue 18 mois de service militaire dans le 8e régiment d’artillerie de campagne à Nancy (Meurthe-et-Moselle), qu’il termine comme chef de pièce avec le grade de maréchal des logis.
À une date restant à préciser, la plupart des membres de la famille quitte l’Allier pour monter à la capitale. En 1929, Antoine et Mélanie Brun vivent avec leurs fils Pierre, alors camionneur, et Louis au n° 77, rue des Aqueducs à Gentilly [1] (Val-de-Marne – 94)
Lors des élections municipales du 5 mai 1929, Paul, Louis, Brun, devenu terrassier, est candidat (à 23 ans) sur la liste du Bloc ouvrier et paysan à Gentilly.
Le 15 août 1931, il adhère au syndicat CGTU des mineurs de la région parisienne.Pendant un temps, il fait fonction d’aide-conducteur de travaux souterrains pour la construction de tunnels du métro.
Il se déclare toujours terrassier en 1933, puis charretier en 1935 et au moment de son arrestation.
Le 13 juillet 1929, Paul Brun se marie une première fois, à Gentilly, avec Marie Mascala, 19 ans, typographe, jusque-là domiciliée chez ses parents au 89, rue Benoît-Malon ; le couple a un enfant, Roger, né en 1933.
Le 3 décembre 1933, Paul Brun est élu conseiller municipal de Gentilly sur la liste du Parti communiste dirigée par Henri Bollot et Charles Frérot. Mais la préfecture de la Seine prononce la dissolution du conseil (14-1-1934). C’est alors que Paul Brun adhère au PC, parrainé par Bollot et Bonnissant. Le 18 février 1934 et le 12 mai 1935, Paul Brun est réélu sur la liste dirigée par Georges Beaugrand. Trésorier puis secrétaire de cellule, membre du comité de section puis trésorier, Paul Brun suit des cours élémentaires du PCF en 1936 et les cours régionaux en 1937. Il rédige des articles pour les journaux de cellules.
Il est également membre de la Fédération des sous-officiers de réserve républicains, crée en 1936, et du mouvement Paix et Liberté .
Son épouse abandonne bientôt le foyer, reprochant à Paul Brun son trop grand engagement politique (lejugement de divorce sera prononcé le 2 décembre 1937). Leur fils Roger est alors pris en charge par son oncle, Félix Brun, frère de Louis, et surtout par l’épouse de celui-ci, Marguerite (sœur de son ex-femme), qui s’est arrêtée de travailler pour élever leur fille Odette, née en 1931.