La chiesa, fondata nel IV secolo da san Gaudenzio, vescovo di Brescia, fu ricostruita fra il 1440 e il 1447 e rimaneggiata nel XVII secolo.

La facciata, di severa struttura quattrocentesca, ha un portale in pietra con arco sorretto da due colonne del primo Cinquecento, affiancato da archi ogivali, resti delle tombe Maggi e Paitone.

L’interno, a croce latina con tre navate, è stato totalmente rimaneggiato nella prima metà del Seicento da Girolamo Quadrio, che incorporò gli antichi pilastri in cotto in altri imponenti in pietra; dell’originaria struttura Quattrocentesca rimangono solamente la cappella del Santissimo Sacramento, quella di Santa Maria, con affreschi di scuola foppesca, e l’abside poligonale.

La chiesa conserva importanti opere d’arte: sul primo altare a destra Assunta di Francesco Paglia, sul terzo Strage degli innocenti di Moretto (1531), nella cappella dopo il quarto altare Madonna col Bambino, tavola ridipinta da Moretto, incorniciata da un ricco rivestimento marmoreo di Alessandro Callegari. Nel presbiterio Crocefisso ligneo di scuola bresciana (1480) con, dietro, numerose opere del Moretto. Sulla destra si apre la sagrestia, ricca di numerose tele.

Accanto alla cappella di Santa Maria, nel transetto sinistro, si apre la cappella del Santissimo Sacramento, che ospita al suo interno un notevole complesso pittorico, formato da dipinti di Romanino e di Moretto con cui i canonici della chiesa stipularono un contratto nel 1521 affidando a ciascuno una delle due pareti. Moretto dipinse a destra: La raccolta della manna, Elia destato da un  angelo, San Luca e San Marco, Ultima cena, e sei Profeti. Romanino dipinse a sinistra: Resurrezione di Lazzaro, San Matteo e San Giovanni evangelista, Cena in casa del fariseo, Profeti. Entrambi i cicli di dipinti sono caratterizzati da un forte senso plastico, da una luminosità particolare, e da un’iconografia antiretorica delle figure, inserite in paesaggi dalle tonalità composte.

Nella chiesa sono conservate altre due opere di Romanino: l’opera giovanile Madonna con Bambino e Santi, sopra il quarto altare a sinistra e Sposalizio della Vergine nella parete sinistra del battistero. Sulla destra della chiesa si apre un elegante chiostro a doppio loggiato del 1487 circa.