Gotycki kościół zbudowano najprawdopodobniej na początku XV stulecia. Zlokalizowany jest na wysokim wzgórzu i otoczony starym murem z kamienia. Jest budowlą orientowaną, jednonawową, z prezbiterium niższym i węższym od nawy, zamkniętym prostą ścianą. Od północy do prezbiterium dobudowana jest zakrystia a do nawy od zachodu – kruchta. Obie dobudówki powstały później niż prezbiterium czy nawa. Łuk tęczowy jest półkolisty, a we wschodniej ścianie prezbiterium umieszczona jest kwadratowa wnęka przeznaczona na oleje święte. Kościół przykryty jest stromymi gontowymi dachami. Zachodnią fasadę wzmacniają na narożnikach ukośne, kamienne szkarpy. Zachowały się też gotyckie detale kamieniarskie; okna mają ostrołukową kamienną oprawę, podobnie trzy wykonane z kamiennego ciosu portale drzwiowe.
W wieku XVI kościół był odnawiany. Poświadczają to daty i nazwiska wyryte w tynku pokrywającym ściany prezbiterium. Na ścianie tęczowej jest napis: Frater Matias 1565., chyba informujący kto był autorem projektu a zarazem kierownikiem budowy. Potem kościół płonął jeszcze dwukrotnie: w roku 1630 i w 1742. Gruntownie odnowiono go w roku 1836. Trzeci wielki pożar miał miejsce w roku 1944, podczas działań wojennych. W trakcie prac zabezpieczających prowadzonych w latach 1945 – 49 odkryte zostały gotyckie polichromie. Są one na ścianach, w glifach okien, na podniebieniu arkady tęczowej. Na ścianie wschodniej zachowały się ślady Ukrzyżowania z postaciami Matki Boskiej i św. Jana Ewangelisty, zaś na ścianie północnej w górnym rzędzie namalowany jest Chrystus w mandorli a po jego bokach apostołowie.
Wzniesienie na którym wzniesiono kościół Wszystkich Świętych, według legendy, nosi nazwę Wzgórza Szydły, legendarnego zbója, a potem założyciela miasta. Szydło, w przerwach kiedy nie był zajęty napadaniem na kupieckie karawany, zamieszkiwał podobno w jaskini pod tym właśnie wzgórzem. Jedna z legend mówi, że dość długo Szydło prowadził ów niecny, zbójecki proceder, ale że wszystko mieć musi swój kres, zdarzyło się raz, że jeden z napadniętych przez bandę Szydły kupców wezwał na ratunek Wszystkich Świętych. Na takie wezwanie pojawił się niezwłocznie zakuty w zbroję konny rycerz. Ponieważ zarówno rycerz jak i dosiadany rumak mieli nadnaturalne rozmiary, wprawiło to całą szajkę w panikę. Zbójcy rozpierzchli się, a ich herszt przeraził się do tego stopnia, że postanowił odtąd żyć uczciwie, a jako zadośćuczynienie za wyrządzone krzywdy, wybudować miasto Szydłów i kościół Wszystkich Świętych.
źródło: