Świątynia ta została ufundowana w 1394 roku przez Dymitra z Goraja, który był od 1377 r. właścicielem Szczebrzeszyna. W styczniu 1398 r. powstaje parafia łacińska w Szczebrzeszynie, którą powołuje arcybiskup halicki Jakub. Wtedy parafia zajmowała większy obszar powiatu szczebrzeszyńskiego, co miało wpływ na życie religijne nie tylko tego regionu, ale i całego kraju. W kronikach jest też wzmianka o jednym z proboszczów Szczebrzeszyna (Walenty Herburt), który był posłem Królestwa Polskiego na Soborze Trydenckim. Po Dymitrze z Goraja właścicielem Szczebrzeszyna zostaje Andrzej Górka, zwolennik reformacji, który w roku 1570 zamienia świątynię na zbór kalwiński. Trzynaście lat później w 1583 r. podczas wielkiego pożaru miasta płomieniom ulega również kościół. W latach 1610 – 1620 pierwszy dziekan i proboszcz szczebrzeszyński, ksiądz Mikołaj Kiślicki (prałat lwowski i oficjał chełmski) na miejscu spalonego drewnianego kościoła wznosi własnym nakładem świątynię murowaną, którą w 1620 r. konsekruje biskup chełmski Jerzy Zamoyski i nadaje jej imię św. Mikołaja. Ponownie kościół płonie pomiędzy rokiem 1644 a1648 (podpalenia dopuścili się Tatarzy), po czym kolejny raz zostaje odbudowany w 1668 roku przez miejscowego proboszcza Jana Unikowskiego. W 1754 r. kościół pali się znowu, jednak płomienie nie powodują większych szkód. Świątynia przetrwała wszystkie zawieruchy historyczne, w tym I i II wojnę światową, bowiem podczas II wojny światowej władze hitlerowskie zamknęły kościół dzięki czemu unikną dewastacji. Kościół wznowił działalność duszpasterską jako rzymskokatolicki kościół parafialny 25 lipca 1944 r. (tuż po wyzwoleniu szczebrzeszyna).