Paul Brundsaux est l'un des héros de la Légion. Sa silhouette illustre le monument aux morts de la Légion à Aubagne. Né le 4/10/1855, il a enchainé les campagnes coloniales. Dans ses souvenirs, le général Tahon en fait un portrait détaillé :"Officier sortant de Saint Cyr, d'une très bonne famille des Vosges, son père étant docteur en médecine, Brundsaux était lieutenant au 4e zouaves à Tunis lorsqu'il fit connaissance d'une jeune chanteuse au café concert. Enthousiste comme il l'était, il se donna entièrement à sa conquête, pourtant facile et pendant quelques mois mena joyeuse vie. Mais un jour, sa maitresse lui ayant annoncé qu'elle était enceinte, il ne douta nullement qu'il fût le véritable père et, malgré les conseils de son colonel, les prières de son père accouru à Tunis, il voulut à tout prix épouser la future maman. L'autorisation de se marier lui étant refusée, il donna sa démission pour épouser librement la mère de son enfant. Pour vivre il se fit alors voyageur de commerce en mercerie et il ne réussit pas. Il était dans la misère lorsqu'il apprit un beau jour qu'il était possible de reprendre du service à la Légion à titre étranger et après quelques démarches, il obtint sa nomination de lieutenant au 2e étranger au Tonkin. Il partit avec femme et enfant et mena là bas la vie dure de premier conquérants de notre grande colonie. Plusieurs fois attaqué, il fit avec sa femme le coup de feu pour disperser les pirates et les pavillons noirs afin de se frayer un passage dans la brousse. Revenu en Algérie au bout de quelques mois, il partit au Dahomey où avec la croix de chevalier, il gagna son grade de capitaine au titre français. Il fit ensuite la première campagne de Madagascar où il se distingua, fut cité et promu chef de bataillon, ayant ainsi en six mois rattrapé ses camarades de promotion. En rentrant il eut à bord un duel avec un camarade et à son arrivée à Oran mena quelques jours la grande vie. Son grand plaisir le soir était de se rendre en compagnie de jeunes officiers dans les cafés concerts, exigeant de l'orchestre qu'il joue immédiatement la marche de la légion, faute de quoi il brisait tables, chaises et bocks. Je le perdis ensuite de vue. J'ai pourtant appris qu'il avait fait campagne au Maroc et qu'il avait terminé sa carrière comme général gouverneur de la Corse. Il avait peu de temps après son retrour de Madagascar, abandonné femme et fille pour s'acoquiner avec une negresse."
Il commandera des brigades actives durant la guerre. Il est mort le 2/1/1930.