Próby założenia parafii trwały aż 40 lat. Były czynione w Komisji Rządowej Wyznań Religijnych i Oświecenia Publicznego w Warszawie, w Rządzie Gubernialnym w Lublinie, w Diecezji Chełmskiej i Biskupstwie Lubelskim. Budowę kościoła rozpoczęto 21 kwietnia 1855 r., a ukończono w 1856 r. Budowniczym kościoła był Konstanty Hendiger z Krasnegostawu. Wybudowano kościół murowany, jednonawowy, w stylu eklektycznym. W ołtarzu głównym, drewnianym, klasycystyczno-barokowym, umieszczono piękny obraz Matki Bożej Milejowskiej zwanej Serdeczną, pochodzący prawdopodobnie z nieistniejącego już kościoła greckokatolickiego. Organy zbudowała stara firma warszawska Mateusza Mielczarskiego. Konsekracji kościoła dokonał 2 października 1858 r. ordynariusz diecezji lubelskiej bp Walenty Baranowski.
Ze względu na potrzeby wiernych, w latach 1990 — 1996 rozbudowano kościół parafialny. Prezbiterium wówczas przeniesiono do nowej części.
Proboszczowie parafii
Imię i nazwisko Daty przejęcia i zejścia z urzędu Uwagi Ks. Henryk Jaskorski 1859 — 1863 Za jego urzędowania wzniesiono kościół;