Fils naturel de Marie Robinaud, Paul Robinaud (orthogaphié également Roubineau) était arrivé début décembre 1896 à Paris pour « se lancer à fond dans le mouvement anarchiste ». Auparavant il avait travaillé à Bordeaux comme garçon boulanger puis comme employé dans un magasin alimentaire (« au Faisan Doré ») et comme cocher.
En janvier 1894 il avait été arrêté à Bordeaux avec l’ouvrier verrier Jean Faure (19 ans) et l’employé de commerce Maurice Malassin (17 ans) pour affichage de placards anarchistes. Tous trois avaient été écroués.

Il participait dans la capitale à de nombreuses réunions où il faisait l’apologie de la propagande par le fait, de Ravachol, Vaillant, Emile Henry et glorifiant les « martyrs de Montjuich » en Espagne.

Par la suite il circulait dans diverses régions de France où il donnait des conférences. Le 9 octobre 1897, la conférence qu’il devait tenir à Fourchambault avait été annulée n’ayant réuni qu’une dizaine de jeunes gens et le président du Syndicat des limonadiers, une certain Lacour. Le lendemain, la police signalait qu’il aurait quitté la localité à destination de Paris avec deux voyageurs de commerce, Léotard (21 ans) et Marius Duchêne (22 ans, né à Paris). Lors de ses déplacements dans les centres ouvriers de la Nièvre, il était souvent accompagné par l’ouvrier métallurgiste Lérault.
Fin 1897 il était toujours signalé comme circulant, à pieds ou en train, dans la région (Nevers, Bourges, Imphy…)

Robinaud avait été maintenu sur la liste des anarchistes de la Seine, lors de la révision de 1900-1901.

Il avait été signalé disparu de Bordeaux pur une destination inconnue en septembre 1902. L’année suivante la police signalait qu’il ne fréquentait plus les milieux anarchistes, mais plutôt des « groupes aux idées nationalistes » et avait été rayé de la liste des anarchistes.