Pierwszy kościół w Sokołowie został ufundowany 12 maja 1415 r. przez Mikołaja Sepieńskiego, właściciela majątku, doradcę i sekretarza wielkiego księcia Witolda. 3 października 1424 r. Grzegorz, biskup włodzimierski, erygował i uposażył parafię w dziesięcinę z Sokołowa i okolicznych wsi.
Po Sepieńskich właścicielami dóbr zostali Sokołowscy, a następnie, na początku XVI w., po bezpotomnej śmierci Stanisława Sokołowskiego – Kiszkowie. Jan Kiszka, starosta żmudzki i podczaszy litewski w 1562 r. zamienił kościół katolicki na zbór ariański. Tę funkcję budynek pełnił do 1592 r. – następnie zwrócono go katolikom. Kolejne drewniane świątynie wznoszono w 1632 r. (za Radziwiłłów), 1737 r. (za Krasińskich). W 1800 r. w Sokołowie wybudowano kolejny kościół parafialny, z fundacji rodziny Ogińskich. Prawdopodobnie poprzednia świątynia spłonęła w 1797 r. w pożarze, który strawił prawie całe miasto. Nowy kościół, pw. św. Michała Archanioła, był również drewniany i uległ pożarowi w 1817 r. W związku z tym ówcześni właściciele Sokołowa: Karol Kobyliński i jego żona Franciszka z Wojewódzkich ufundowali nowy, tym razem murowany kościół pw. św. Michała Archanioła. Budowa trwała od 1820 do 1826 r. W tym okresie funkcję świątyni parafialnej pełniła drewniana kaplica pw. św. Rocha, znajdująca się w pobliżu. W 1826 r. kościół został poświęcony. Obiekt wzniesiony przez Kobylińskich nie przetrwał II wojny światowej. W nocy z 26 na 27 lipca 1944 r. sowieckie lotnictwo zbombardowało miasto, w wyniku czego kościół, plebania i wikarówka uległy zniszczeniu. Po wojnie funkcję świątyni parafialnej przejął ponownie drewniany kościółek św. Rocha. Nowy kościół zaczęto wznosić w 1948 r., według projektu warszawskiego architekta Andrzeja Boni. Otrzymał wezwanie Niepokalanego Serca Najświętszej Maryi Panny. Prace, którymi kierował ówczesny proboszcz sokołowski ks. Stanisław Pielasa, zakończono w 1953 r. Tego roku ks. Ignacy Świrski, biskup siedlecki czyli podlaski, konsekrował nowy kościół. Dopiero w 1983 r. ukończono wznoszenie wieży wieńczącej fasadę świątyni i wyposażanie jej wnętrza: ułożono posadzkę z terakoty, wzniesiono trzy ołtarze, zakupiono trzy konfesjonały, ławki, organy i dwa nowe dzwony. W późniejszym okresie w prezbiterium umieszczono ołtarz projektu prof. Gustawa Zemły z płaskorzeźbą Chrystusa Zmartwychwstałego jego autorstwa. Boczne figury wykonał Dariusz Kowalski z żoną, natomiast rzeźba Matki Bożej, przywieziona w 1953 r. z Piekar Śląskich, została umieszczona w centrum kompozycji w 1992 r., gdy kościół został na mocy bulli papieża Jana Pawła II podniesiony do rangi konkatedry. W 1999 r. do tylnej elewacji kościoła dostawiono drewniany ołtarz polowy, będący częścią ołtarza zbudowanego w Drohiczynie z okazji wizyty Jana Pawła II.
Architektura kościoła pw. Niepokalanego Serca NMP łączy w sobie cechy modernizmu i historyzmu. Kubiczne bryły korpusu, prezbiterium i wieży, pozbawione praktycznie podziałów architektonicznych, zestawione zostały z gotycyzującym detalem, np. 
zakończonymi ostrymi łukami oknami wypełnionymi maswerkiem. Andrzej Boni wykorzystał w projekcie kościoła sokołowskiego rozwiązania i formy zastosowane przez niego wcześniej w świątyni pw. Najczystszego Serca Maryi w Warszawie. Kościół ten, wystawiony w latach 1934 – 1940 na pamiątkę setnej rocznicy bitwy pod Olszynką Grochowską, jest pierwowzorem konkatedry w Sokołowie.
W I – szej połowie XIX w. przy bramie na osi głównego wejścia do świątyni wybudowano do dziś istniejącą murowaną dzwonnicę. Na terenie dawnego cmentarza zachował się nieco uszkodzony i przerobiony nagrobek z około 1855 r. ks. Czarnockiego. Znalazła też tam swoje miejsce mogiła Kobylińskich, których szczątki spoczywały w krypcie poprzedniego, ufundowanego przez nich kościoła. Ma ona formę prostego żelaznego krzyża – nieco uszkodzonego – umieszczonego na polnym kamieniu. W obrębie ogrodzenia znajdują się trzy drewniane krzyże oraz kapliczka, powstała około 1919 r., z figurą Chrystusa Miłosiernego, który lewą dłonią wskazuje na serce z płomieniem.
