Svolse la maggior parte della sua attività in Spagna tanto da essere considerato come appartenente al Rinascimento spagnolo. Discendente da una famiglia originaria di San Valentino di Castellarano, era il quarto figlio di Pietro Lazzaro da San Leocadio. È documentata la sua presenza a Reggio fino al 1458, quando Paolo aveva 11 anni. Probabilmente poco tempo dopo si trasferì a Ferrara, dove si formò presso Bono da Ferrara ed Ercole de Roberti, subendo l'influenza di Andrea Mantegna, Cosmè Tura e Francesco del Cossa.
Imbarcatosi probabilmente ad Ostia nel 1472 al seguito del giovane e potente cardinale Rodrigo Borgia, il futuro papa Alessandro VI, iniziò subito la sua attività a Valencia dove si trovano le sue opere più importanti, fra le quali citiamo gli affreschi nella cattedrale di Valencia, scoperti nel 2004 nel corso di lavori di restauro che hanno comportato la rimozione di una sovrastruttura barocca a volta che li nascondeva. Gli affreschi rappresentano scene bibliche, fra le quali la Vita della Vergine che è ritenuta la prima opera del Rinascimento in Spagna, e gli Angeli musicanti che possono essere considerati il capolavoro di Paolo. L'attribuzione di queste opere è confermata dai documenti presenti nell'archivio della cattedrale.
Danilo Morini, Giovanni Pio Palazzi, Benedetto Morini - Un pittore reggiano in Spagna - Paolo da San Leocadio; da Reggio Storia n° 114, Reggio Emilia 2007.
Ximo Company i Climent - Paolo da San Leocadio i els inicis de la pintura del Reinaixement a Espanya, Gandia 2007.
Ximo Company, Il Rinascimento di Paolo da San Leocadio, Palermo, Gruppo editoriale Kalos, 2009
Stefania Rusconi, Ximo Company, "Nuevos datos documentales sobre Paolo da San Leocadio", da "Ars Longa" n° 22, Valencia 2013.