Paul Nénot apprend l'architecture très jeune, puisque sa mère le fait travailler dès l'âge de 13 ans, en 1866, dans l'atelier de Paul-Eugène Lequeux. Après divers travaux dans l'atelier de Charles-Auguste Questel qui dirigeait à ce moment-là un des ateliers officiels de l'école des Beaux-Arts, il se mobilise dans les Francs-Tireurs de la presse qui défend La Courneuve et Le Bourget contre l'invasion prussienne. En 1871, après avoir été démobilisé et afin de financer ses études, il travaille pour le compte de Charles Garnier. Reconnaissant de son talent, Charles Garnier n'hésita pas à appuyer Nénot pour qu'il évite le service militaire long de 5 ans à l'époque.
L'année 1875 marque le premier concours remporté pour la reconstruction d'une école à Huy en Belgique. Avec son ami sculpteur Eugène-André Oudiné, Nénot est en charge de l’exécution. Avec Oudiné il réalise aussi un immeuble de rapport situé boulevard Pereire pour le compte de la Société Parisienne Mobilière, et le théâtre des Arts à Rouen.
1877 est l'année de tout les succès. Il remporte le Grand prix de Rome et les commandes se succèdent. En 1882, il remporte le concours pour la construction de la nouvelle Sorbonne. Les critiques pleuvent et nombreux sont ceux qui doutent de sa capacité à assumer ce chantier. Charles Garnier se porte alors garant. C'est en juillet 1901 qu'est livré ce qui a constitué l'un de ses plus grands chantiers : "la Nouvelle Sorbonne".
En 1915, il devient membre de l'Académie Française.
Entre 1931 et 1937, il dirige l'équipe (Julien Flegenheimer, Camille Lefèvre et Carlo Broggi, Joszef Vago) dédiée à la construction du célèbre Palais des Nations pour le compte de la Société des Nations à Genève.
A noter aussi qu'il fut l'associé de Julien Flegenheimer.