Essa era già nota nel 1208 col nome di S. Gregorio e aveva davanti a sé una piccola piazza porticata, destinata al mercato del pesce; quest'ultima, insieme alle piazze delle Erbe (ora piazza Palazzo di Città), del Grano (oggi piazza Corpus Domini) e del Burro (attualmente è un cortile all'interno del Municipio, la cort dël bur), faceva parte di un ampio sistema mercatale. La chiesa dava il nome alla Torre civica (situata di fronte, all'angolo con l'attuale via Garibaldi), che era appunto detta "Torre di San Gregorio". Nell'edificio attuale, a ricordare la chiesa antica è rimasta, in una nicchia a destra dell'ingresso, una piccola Madonna in pietra in stile gotico assisa su un trono, datata 1375. L'erezione della nuova chiesa in stile barocco risale al 1667 ad opera dell'architetto  Lanfranchi. Al termine del XIX secolo la chiesa venne decurtata in facciata per consentire l'allargamento della via antistante.

La trecentesca "Madonna delle Grazie" è tutto ciò che resta della chiesa medievale di San Gregorio: questo edificio aveva di fronte a sé una piccola piazza nella quale si teneva il mercato del pesce.