Il nucleo originario della chiesa fu costruito, secondo gli storici locali, a cavallo tra XIII e XIV secolo, epoca di massima diffusione del culto di San Nicola di Bari, che secondo una tradizione locale aveva preservato dalla morte alcuni abitanti del paese partiti per le crociate (Meucci,p. 63). L’antica torre del Castrum Sancti Pauli divenne la torre campanaria, la quale conserva ancora una campana che risale al 1390. Una lapide custodita all’interno ci informa che la chiesa venne “ricostruita ed ampliata” nel 1587. Il campanile fu invece abbattuto da un fulmine e ricostruito per volere del Vescovo di Tivoli Marcello Santacroce nel 1669 (data incisa sulla volta interna). La cupola ottagonale e la sua decorazione sono attribuite all’architetto Guidetto Guidetti (Felici, p. 97), architetto anche della chiesa cesiana di Santa Caterina dei Funari a Roma. L’edificio fu di nuovo rinnovato nel 1910, quando il pittore Mario Agrifoglio ne dipinse il soffitto e le pareti.