La chiesa, dedicata a Paolo di Tarso, venne edificata tra il VII e l'VIII secolo, subendo più volte rimaneggiamenti e ampliamenti nel corso dei secoli oltre che essere affiancata da edifici che ne celavano parzialmente la vista. L'attuale aspetto deriva dall'abbattimento del vecchio palazzo municipale, avvenuto negli anni sessanta del XX secolo.[1]
Dopo la sua secolarizzazione, l'edificio, oramai spoglio di ogni arredo sacro e delle reliquie in esso contenute, come tra l'altro le ossa di san Sabino conservate nella cripta realizzata nel XIII secolo, venne ceduto al Comune di Monselice, il quale dopo averne cambiato la destinazione d'uso ad auditorium, ne abbandonò la funzione per la difficoltà di migliorarne l'acustica. Dai primi anni del duemiladieci è sede del Museo San Paolo, che affianca alla collezione di reperti archeologici la vista delle fondamenta delle strutture degli edifici originari.[1]
