Fondata agli inizi del Seicento nel nucleo più antico del centro storico di San Paolo di Civitate, una piccola cittadina dell'Alto Tavoliere, la chiesa dedicata a San Nicola Vescovo fu il primo edificio di culto costruito all'interno delle mura. A seguito del terribile terremoto del 1627 la chiesa fu quasi rasa al suolo. Restaurata nel corso del Seicento, divenne sede stabile della Confraternita del Rosario nel 1780. Con l'aumento della popolazione e dei confratelli si avvertì la necessità di ampliare il corpo di fabbrica che, per voto di guarigione del priore, fu interamente ricostruito nelle fattezze attuali tra il 1801 e il 1804, più imponente del sacello originario e dotato di un corpo per il presbiterio ed il coro. L'impianto ad aula unica di forma ellittica con volta a catino, gli stucchi ornamentali interni e la facciata a doppio ordine con timpano sovrastante, risentono ancora degli ultimi echi del tardo barocco pugliese.