Pierwszy drewniany kościół w Sokołowie Podlaskim (dawniej: Sokołowo) pw. Trójcy Przenajświętszej, św. Michała Archanioła, św. Małgorzaty Dziewicy i Męczennicy ufundował w niedzielę Exaudi, czyli 12 maja 1415 r., dziedzic Sokołowa - Mikołaj Sepieński z Sepna h. Nowina, doradca i sekretarz (1413-24) wielkiego księcia litewskiego Witolda Aleksandra (ok. 1348-1430) i sędzia ziemi poznańskiej (1426-30). Świadkami tego wydarzeni byli: ks. Grzegorz z Buczkowa (zm. ok. 1424 r.), biskup włodzimierski (1400-24), i Scibor z Sochocina (zm. po 1431 r.), podkomorzy ciechanowski. Jak zaznacza dokument fundacyjny, pierwszym plebanem tegoż kościoła został ks. Jan Czamsor. W zamian za otrzymane beneficjum (m.in. Przeździatka, Rogowo) miał on obowiązek utrzymywać dwóch wikariuszy i szkołę.
Na prośbę wspomnianego Mikołaja Sepieńskiego we wtorek po święcie św. Michała Archanioła, czyli 3 października 1424 r., wspomniany biskup włodzimierski erygował w Sokołowie parafię katolicką, uposażając ją m.in. w nastepujące wsie: Rogów, Przeździatka, Nieciecz, Bielany. W tym samym roku, a dokładnie 30 marca 1424 r. wielki książę litewski Witold Aleksander dokonał lokacji miasta - na prawie średzkim. W latach 1472-74 plebanem sokołowskim był ks. Jakub.
W 1508 r. bezpotomny Stanisław Sokołowski, wnuk fundatora i ostatni z rodu Sepieńskich vel Sokołowskich, zapisał dobra sokołowskie swemu krewnemu, dziedzicowi Ciechanowca - Stanisławowi Piotrowiczowi Kiszce h. Dąbrowa (zm. 1514 r.), marszałkowi hospodarskiemu (1492-1509), hetmanowi wielkiemu litewskiemu (1503-07).
1 lipca 1569 r. król Polski Zygmunt II August (1520-72) potwierdził darowiznę Anny Radziwiłł (1525-1600), wdowy po Stanisławie Kiszce (zm. 1554 r.), wojewodzie witebskim (1544-54), miasta Sokołowa i należących do niego wsi na rzecz jej syna Jana Kiszki (1547-92), krajczego litewskiego (1569 r.), starosty żmudzkiego (1579-89), kasztelana wileńskiego i wojewody brzeskiego (1588 r.). Jan Kiszka, który był gorliwym zwolennikiem arianizmu, ok. 1558 r. siłą zabrał kościół katolikom, zamieniając go na zbór ariański. Na ten czas zarząd i duszpasterstwo przejęła parafia Suchożebry. 1 lipca 1569 r. Zygmunt August potwierdził darowiznę Sokołowa i wsi należących do niego, dokonaną przez Annę z Radziwiłłów, na rzecz wspomnianego zwolennika arian - Jana Kiszki (1547-92). Od 1592 r. właścicielami Sokołowa stali się Radziwiłłowie, którzy po przyjęciu kalwinizmu popierali innowierców oraz dyzunitów (po 1596 r.). Od 1590 r. kościół sokołowski znów znajdował się w posiadaniu katolików. Kolejnymi właścicielami miasta były rodziny: Krasińskich (1668 r.), Łużeckich (przed 1686 r.), Ogińskich (1764 r.), Kobylińskich (1808 r.), Hirschmanów (1843 r.), Sobańskich (1904 r.) i Malewiczów (1924-44).
W 1800 r. ówczesny proboszcz - ks. Tomasz Kosieradzki, kosztem miejscowego dziedzica, wzniósł drewniany kościół pw. św. Michała Archanioła, który 3 października 1817 r. uległ doszczętnie pożarowi. W tej sytuacji kolejni dziedzice Sokołowa - marszałek powiatowy łosicki Karol Kobyliński, zwany Książko (1764-1842), i jego żona Franciszka Wojewódzka (1765-1827) ufundowali w latach 1820-26 niewielki, murowany kościół pw. św. Michała Archanioła. W 1826 r. został on poświęcony.
Wspomniani fundatorzy w 1819 r. pod kierunkiem ówczesnego proboszcza - ks. Franciszka Dąbrowskiego wznieśli drewniany kościół pw. św. Rocha przy ul. Kossowskiej, który służył wiernym podczas wznoszenia nowej świątyni. W 1981 r. został on przeniesiony na obecną ul. św. Rocha.
Murowana świątynia Kobylińskich przetrwała aż do czasów II wojny światowej. Z 26 na 27 lipca 1944 r. legła ona w gruzach, zbombardowana przez lotnictwo wojsk sowieckich. Funkcję tymczasowej kaplicy przejął wówczas kościół pw. św. Rocha. Na miejscu zniszczonej świątyni parafialnej w 1948 r. przystąpiono do wznoszenia obecnego kościoła pw. Niepokalanego Serca Najświętszej Maryi Panny. Jego projekt wykonał arch. Andrzej Boni (zm. 1964 r.) z Warszawy, który wzorował się na wcześniejszym swoim planie kościoła pw. Najczystszego Serca Najświętszej Maryi Panny na pl. Szembeka w Warszawie. Fundamenty poświęcił w czasie wizytacji kanonicznej 5 września 1948 r. ks. Ignacy Świrski (1885-1968), biskup siedlecki, czyli podlaski (1946-68). Prace budowlane, którymi kierował ks. kan. Stanisław Pielasa (1906-85), proboszcz sokołowski (1946-83), ukończono w 1953 r. Tego samego roku 25 października odbyła się konsekracja, której dokonał wspomniany bp Ignacy Świrski. Na mocy bulli Jana Pawła II Totus Tuus Poloniae Populus 25 marca 1992 r. kościół ten został podniesiony do godności konkatedry.
Z obiektów zabytkowych pozostała tylko murowana, dwukondygnacyjna dzwonnica, zbudowana w pierwszej połowie XIX wieku. Obok kościoła stoją: dom dla organisty i kościelnego, zbudowany w latach 1957-61, oraz murowana plebania (mieszkania księży wikariuszy i kancelaria), zbudowana w latach 1947-50 staraniem ks. kan. Stanisława Pielasy. Z drugiej strony kościoła znajduje się dom parafialny (mieszkanie księdza proboszcza i sale parafialne), wzniesiony w latach 1986-89 staraniem ks. inf. Jana Sobechowicza.

Bibliografia:
Archiwum diecezjalne w Drohiczynie. III /Q/. Akta parafii Sokołów Podlaski 1817-1980. 1981-1991; P. Aleksandrowicz, Diecezja siedlecka, czyli podlaska, Sadowne 1956; I. Galicka, H. Sygietyńska, Województwo warszawskie. Powiat sokołowski (Katalog zabytków sztuki w Polsce t. X, z. 25), Warszawa 1965; M. Głowacki, Katalog duchowieństwa i parafii diecezji siedleckiej, czyli podlaskiej, Siedlce 1985; Katalog kościołów i duchowieństwa diecezji siedleckiej, czyli podlaskiej na rok 1929, Siedlce 1929; J. Kazimierski (red.), Dzieje Sokołowa Podlaskiego i jego regionu, Warszawa 1982; A. Kołodziejczyk, P. Matusak (red.), 575-lecie Sokołowa Podlaskiego, Siedlce 2000; M. Pietrzak, Sokołów Podlaski dawniej i dziś, Siedlce 1992; tenże, Kościoły i cmentarze ziemi sokołowskiej, Sokołów Podlaski 2002; S. Ulaczyk (oprac.), Rocznik diecezji drohiczyńskiej. Spis parafii i duchowieństwa 1999, Drohiczyn 1999.

Domy zakonne:
Zgromadzenie Córek Maryi Wspomożycielki (Salezjanki) - FMA. W parafii od 1987 r., ul. Kosowska 26, 08-300 Sokołów Podlaski, tel. (0-25) 781-23-72
Zgromadzenie Sióstr Służek Najświętszej Maryi Panny (Służki) - SNMPN. W parafii od 1904 r., ul Kościuszki 4, 08-300 Sokołów Podlaski, tel. (0-25) 781-28-68

Porządek Mszy św.:
- niedziele i święta:
- kościół parafialny: 6.30, 8.00, 9.30, 11.00, 12.30, 16.00, 20.00 (raz w miesiącu dla przedszkolaków: 14.30 i podobnie dla kandydatów do sakramentu bierzmowania)
- święta niebędące dniami wolnymi od pracy:
- kościół parafialny: 6.30, 7.00, 7.30, 17.00 (według czasu letniego: 18.00, w środy i czwartki: 11.00)

Odpusty w parafii:
Niepokalanego Serca Najświętszej Maryi Panny, św. Rocha (niedziela po 15 sierpnia)
Nabożeństwo adoracyjne: 27-29 września; co tydzień: środa - czwartek (cały dzień)

Księgi metrykalne:
Księgi chrztów: od 1944 r.
Księgi małżeństw: od 1944 r.
Księgi zmarłych: od 1944 r.