La chiesa risulta già menzionata nel XIII secolo, ma nel corso dei secoli subisce diversi lavori di ristrutturazione, in quanto risulta insufficiente per accogliere tutta la popolazione novese. La facciata è caratterizzata da due campanili laterali e da due volute che fanno da raccordo con il timpano centrale.
La chiesa assume l’assetto definitivo nel 1679 e viene consacrata nel 1684.
Presenta una pianta a croce latina, divisa in tre navate da due file di colonne doppie in pietra. Le navate laterali hanno quattro altari; sul braccio destro del transetto si apre la cappella della Madonna Lagrimosa, sul braccio sinistro quella degli Angeli Custodi.
L’interno è arricchito da innumerevoli stucchi e da numerosi dipinti seicenteschi di scuola genovese. Il penultimo altare a sinistra, intitolato a S. Francesco Saverio, incornicia il dipinto raffigurante la "Predica di San Francesco Saverio" di Andrea Pozzo (Trento, 1642 – Vienna, 1709).
L’altare maggiore in marmi chiari è stilisticamente databile al XVII secolo ed è attribuibile a una bottega genovese: probabilmente fu realizzato tra il 1676, anno di inizio dei lavori di ristrutturazione e restauro dell’interno della chiesa, e il 1684, quando le reliquie di San Vittore furono traslate nel sacello di quest’altare. La mensa, di forma trapezoidale, poggia su due piedi laterali ed è affiancata da due angeli che fungono da telamoni; i tre gradoni superiori presentano una ricca decorazione a foglie d’acanto in marmo bianco.
Di notevole interesse è il gruppo ligneo posto sull’altare maggiore, rappresentante il "Calvario", costituito dal Crocifisso e da quattro statue a grandezza quasi naturale, cave nel retro, raffiguranti la Maddalena, San Giovanni Evangelista, San Pietro e Santa Marta.
Degna di nota è la cappella posta al termine della navata destra, i cui stucchi furono disegnati da Andrea Pozzo: sull’altare seicentesco è collocata una statua lignea del XV secolo nota come "Beata Vergine Lagrimosa", santa protettrice della città. Nella stessa cappella si conservano due importanti dipinti: a Domenico Fiasella è attribuita la tela raffigurante l’"Annunciazione con un donatore" (1660). Il dipinto, dono votivo della famiglia Spinola, fa pendant con la scena notturna della "Natività della Vergine" (1666) del principale collaboratore di Fiasella, l’allievo e cognato Giovanni Battista Casoni.