Di famiglia di umili condizioni, poté frequentare il ginnasio grazie ad un benefattore, ed il liceo al Collegio Gaslini di Pavia ricoprendo il ruolo di prefetto ad esenzione delle spese. Si laureò in fisica e matematica a Pavia con F. Casorati nel 1878. Dopo essersi perfezionato in Germania con una borsa di studio, dal 1884 conseguì la libera docenza all’Università di Padova, dove tenne numerose supplenze e corsi liberi su diversi argomenti, in particolare, dal 1885 al 1920, sulla teoria dei numeri, dei cui sviluppi in Germania fu probabilmente il miglior conoscitore italiano.  Fu professore di matematica al Tito Livio per circa quarant’anni, fino al 1923, quando andò in pensione anche dall’insegnamento universitario, ritirandosi a vivere in una casetta ad Arquà Petrarca. Morì al lido di Venezia.

Oltre ai libri di ricerca, furono importanti i suoi manuali per l’università e le scuole superiori, nei quali introdusse significative ed efficaci novità di contenuto e di metodo (Teoria dei Numeri, 1885; Algebra e Aritmetica generale, 1890; Libro di aritmetica e di algebra elementare, 1896).

Fu socio dell’Accademia patavina e membro attivo dell’associazione di insegnanti medi di matematica Mathesis.

Fra i suoi allievi al liceo e all’università vi fu Tullio Levi Civita (cui oggi è intitolato il dipartimento di matematica dell’università di Padova), che lo ricordò così: “Matematico insigne per acume e dottrina […] insegnante impareggiabile: antico suo scolaro al liceo e all’università, ne ricordo con impressione incancellabile e schietta gratitudine i consigli e gli incoraggiamenti preziosi”. 

Commosso fu anche il ricordo di un altro suo allievo, Virgilio Brocchi,  divenuto poi romanziere:

Paolo Gazzaniga  fu davvero un magnifico maestro non solo di matematica, ma di austerità e di vita. L’ho negli occhi qual era, quando giovanetto, quasi fanciullo, io lo guardavo dal mio banco ritto davanti alla lavagna, alto, pacato, con quella sua bella testa di artista e di asceta, con gli occhi tutta luce; e mi riodo dentro la sua calda voce che si intenerisce parlando di algebra come un poeta si intenerisce parlando della propria passione. E il cuore trabocca di riconoscenza, di ammirazione, di affetto”.

A Paolo Gazzaniga a Padova è intitolata una via.