Un primo tempio dedicato al santo esisteva fin dall'841 all'inizio dell'attuale viale XX Settembre; l'edificio fu in seguito ricostruito e nuovamente consacrato nel 1298. A seguito alla peste del 1576, dalla quale Novara miracolosamente non fu colpita, si decise la ricostruzione della basilica nel punto più elevato della città. Qui, fin dal 1019, esisteva una chiesa intitolata a san Vincenzo Martire, che fu demolita per far posto al nuovo edificio; si salvarono solo tre cappelle, tra cui quella dedicata a san Giorgio dove erano state temporaneamente traslate le spoglie di san Gaudenzio a seguito della distruzione della basilica extra-muraria.

La progettazione fu affidata a Pellegrino Tibaldi, cui sono da ricondurre l'accentuato verticalismo dell'edificio e il senso di vigoroso plasticismo promananti dalla facciata e dai fianchi, mossi entrambi da nicchie, finestroni e colonne poderosamente aggettanti.

La basilica possiede numerose opere d'arte, tra cui un'antica cattedra vescovile. Nello scurolo, di fattura settecentesca, è conservata un'urna d' argento con i resti di San Gaudenzio, patrono della diocesi. Nella cappella del Santissimo Sacramento sono esposte otto tele secentesche del Fiammenghino, che rappresentano scene della vita di San Gaudenzio, svoltasi nella città. La cappella della Natività ospita un polittico di Gaudenzio Ferrari (commissionato nel 1514 circa), appartenente alla primitiva chiesa di San Vincenzo.

Sostanzialmente conforme ai canoni rinascimentali è la cornice (con cornicioni e colonne) delle sei tavole. Nella cappella dell'Angelo Custode sono presenti affreschi di Tanzio da Varallo (1629), raffiguranti i santi protettori della famiglia Nazari (che era la famiglia committente), scene bibliche, il Paradiso e il Purgatorio. Questi dipinti, così come la tela raffigurante la Battaglia di Sannacherib sono il frutto di un gusto che probabilmente già esce dai confini regionali per trovare ispirazione nell'arte dell'Europa centrale. Il campanile è opera di Benedetto Alfieri (1786).

La cupola, edificata tra il 1840 e il 1885 da Alessandro Antonelli, è completamente realizzata in muratura, misura 121 m di altezza e ha un diametro alla base di 31 m. Alla sommità è posta una statua in rame dorato del Cristo Salvatore, opera di Pietro Zucchi (1873).