Kościół św. Mikołaja to najważniejszy zabytek Przybynowa. Wzniesiono go najprawdopodobniej w połowie XVI w. z kamienia, w miejscu drewnianego, istniejącego około 250 lat, a wspominanego w 1306 i 1470 r. Pierwszy murowany kościół ufundowała rodzina Myszkowskich. Był krótszy o 1/3 od obecnego, kryty gontem, bez sklepienia. Pierwotnie renesansowy, w 1770 r. z fundacji hrabiego Adama Męcickiego został przebudowany w stylu barokowym. Wtedy też kościół zasklepiono, przyozdobiono ornamentami z gipsu, stacjami Drogi Krzyżowej, popiersiami apostołów, ewangelistów i świętych. Biskup sufragan gnieźnieński Ignacy Kozierowski konsekrował świątynię 22 lipca 1777 r. W pierwszej połowie XIX w. świątynia podupadła, w 1849 r. nawiedził ją pożar, podczas którego stopiły się dwa dzwony na wieży kościelnej. Zastąpiono je nowymi, ale zostały zrabowane przez Austriaków. Te, które można dzisiaj usłyszeć, służą od lat 20. XX w. W 1862 r. kościół poddano gruntownemu remontowi, a hełm wieży pokryto blachą. W 1863 r. kościół ponownie konsekrowano. Dokonał tego administrator diecezji kieleckiej biskup Maciej Majerczak. W latach 1911-1912 staraniem ks. Adama Adamka kościół powiększono, dodając dwa przęsła, arkady, zakrystię i nową wieżę zwieńczoną kopulastym hełmem, na dachu ułożono dachówkę. W latach 1995-1996 dachówka została wymieniona na blachę miedzianą. W kościele warto zobaczyć obraz Matki Bożej z Dzieciątkiem, który podobno ofiarował król Jan III Sobieski. W kronikach zachowały się opisy, iż dawniej ściany i ołtarze zdobiły 24 kryształowe lustra. W 2006 r. przybynowska parafia obchodziła jubileusz 700-lecia istnienia. Jest jedną z najstarszych w gminie Żarki, obejmuje wsie: Wysoką Lelowską, Zaborze, Suliszowice, Ostrów i Przybynów.