La chiesa dedicata a S. Paterniano, patrono della città di Fano, è di stile tardorinascimentale e si articola in strutture ed elementi architettonici sobri ed imponenti.

Il precedente edificio intitolato al Santo era situato fuori del centro cittadino, nella zona dell'attuale Via dell'Abbazia,ove sorge un piccolo edificio esagonale (S. Paternianino) edificato per ricordare l'ubicazione dell'antico complesso monastico.
Secondo la "Vita Sancti Paterniani" del codice Nonantolano (manoscritto del XII secolo conservato presso l'archivio del Capitolo), il Santo morì in questo luogo (360 circa) dopo aver retto la chiesa fanese per quarantadue anni.
Probabilmente sul suo sepolcro si edificò una basilica più volte ricostruita, che dall'ottavo secolo divenne parte di un'abbazia, divenuta benedettina verso la metà dell'XI secolo.
Nel 1479 il monastero passò ai Canonici Regolari di San Salvatore, i quali già dal terzo decennio del 1500 avviarono entro la città di Fano, sull'area della Chiesa di San Nicolò e di alcune abitazioni, i lavori dell'attuale complesso conventuale, per i quali i documenti d'archivio ricordano Magister Stefanus Martini e Magister Petrus Antonii di Como.
Nel 1551 fu traslato nella nuova chiesa il corpo di San Paterniano dalla chiesa extraurbana, mentre nel 1558 si celebrò la consacrazione.

L'esterno dell'edificio non venne mai ultimato con il rivestimento in pietra e ad ornamento della facciata fu eseguito solo il portale di derivazione michelangiolesca del veneziano Jacopo Bambagiani (1573).
Il Monastero, tenuto dai Canonici Regolari di San Salvatore fino al 1860, è passato nel XX secolo ai padri Capuccini.
Il campanile è stato abbattuto nel 1944 dai Tedeschi in ritirata e rifatto nel 1952 su identico disegno (1).

All'interno si trovano dipinti di Alessandro Tiarini, Giambattista Ragazzini, Claudio Ridolfi, un'opera attribuita al Cavalier d'Arpino e un Crocifisso ligneo del napoletano Giacomo Colombo. Nella cappella di San Paterniano il ciclo di dipinti realizzati da Carlo Bononi e Sebastiano Ceccarini racconta la vita del Santo, mentre l'affesco della cupoletta più interna è opera di Antonio Viviani detto il Sordo.
Vi è presente un organo Callido, restaurato nel 2005.

NOTE:
(1) Il campanile è stato inaugurato il 28 ottobre 1952. Quello abbattuto è stato attribuito, come il resto della Basilica, a Iacopo Tatti detto il Sansovino, pur in assenza di documenti probatori.