In 1881 begon hij een studie architectuur in Antwerpen, en kwam dan terug naar Brussel om daar zijn studie af te maken. Hij werd er leerling van de Brusselse architect Félix Laureys die in 1849 de Prijs van Rome voor architectuur had gewonnen.
Hij trad in het huwelijk met Louise Ponselet (1873 - 1947). Uit deze gemeenschap werden twee kinderen geboren:
een zoon: Jacques (1895 - 1947), die eveneens architect werd;
een dochter: Jacqueline (1900 - 1978).
In 1897 kocht hij in Elsene een huis in classicistische stijl. Hij nam er intrek met zijn familie, en liet de woning uitbreiden en verbouwen. Het gebouw staat bekend als Hotel Saintenoy.
Aanvankelijk leverde Paul Saintenoy werk in de Neo-Vlaamse-Renaissance-stijl. Samen met Victor Horta en Paul Hankar stond hij onder sterke invloed van de art nouveau. Deze stijl begon hij te beoefenen in 1899, en vanaf 1904 werkte hij eveneens in de classicistische stijl. Zijn meest bekende en baanbrekende werk was de uitbreiding van het warenhuis Old England in art-nouveau-stijl, anno 1899.
Omdat hij interesse had voor archeologie werkte hij een tijd als algemeen secretaris van de Société Royale de l’Archéologie de Bruxelles. In 1910 begon hij een carrière als leraar architectuurgeschiedenis aan de Koninklijke Academie voor Schone Kunsten in Brussel, een rol die hij 30 jaar zou vervullen. Aan het einde van de Eerste Wereldoorlog werd Saintenoy benoemd tot lid van de Koninklijke Commissie voor Monumenten en Landschappen, waar hij een belangrijke rol speelde in de heropbouw van België na de oorlogsperiode.
Hij schreef verscheidene boeken die de architectuur als onderwerp hadden.
Vlak voor zijn dood werkte hij nog mee aan het Noordstation, dat vooral de stempel draagt van zijn zoon Jacques die vroegtijdig overleed.