Wieś Kamionna powstała pod koniec XV w. Jej początkowa nazwa brzmiała: w 1503 r. Kamienmost, później Kamionlas/Kamionolas (od 1509 r. do końca XVIII w.). Dzisiejsza postać nazwy Kamionna (wcześniej Kamienna) znana jest od 1790 r.
Właścicielem tych terenów, które wchodziły w skład dóbr łochowskich, na przełomie XIV/XV w. był przypuszczalnie Wawrzyniec z Targowego (dzisiaj dzielnica Targówek w Warszawie), wojski (1398-1415), podsędek (1415-1427) i łowczy warszawski (1428). Jest on protoplastą rodu Kuszabów h. Paprzyca, który osiadł w Łochowie, przyjmując nazwisko Łochowski. W 1428 r. dobra te należały do jego syna - Dziersława Targowskiego (zm. ok. 1446), łowczego warszawskiego (1428-ok. 1446). Jego syn Mikołaj Targowski z Łochowa (zm. ok. 1498) ufundował tutaj pierwszy kościół pw. Narodzenia Najświętszej Maryi Panny, św. Jana Chrzciciela i św. Mikołaja. To wydarzenie miało miejsce w „Niedzielę Świętych Królów”, czyli 6 stycznia 1488 r. Z nieznanych jednak przyczyn przerwano budowę w Łochowie i zmieniono lokalizację, kontynuując ją od 1489 r. w Kamionolasie. Należy jednak przypuszczać, że akt fundacyjny został sporządzony w Łochowie, a później - z nieznanych dziś przyczyn - kościół zbudowano w Kamionnie. W 1503 r. współkolatorem tejże świątyni był kanonik pułtuski ks. Marcin Wąsowski, bliski współpracownik ks. Erazma Ciołka h. Sulima (zm. 1522), biskupa płockiego (1503-1522). Tegoż roku czterej synowie fundatora: Jakub, Jan, Mikołaj i Dziersław Łochowscy zobowiązali się wydzielić 3 włóki poświętnego przy kościele oraz dali plebanowi dochody w postaci rączki miodu (jeden bór bartny). Pierwszym plebanem w Kamionolasie został wówczas ks. Piotr (do ok. 1510), a po nim tę funkcję pełnił w latach 1510-1519 ks. Bernard Świerczewski ze wsi Świercze. Kanoniczna erekcja parafii nastąpiła między 1518 a 1524 r. staraniem ks. Ścibora Żelazowskiego (1519-1542).
Drugi kościół ufundował w 1576 r. dziedzic części Łochowa, Twarogów i Lasek Jan Łochowski h. Kuszaba razem ze swoimi braćmi, którzy byli ówczesnymi kolatorami kościoła w Kamionolasie. Konsekracja świątyni, która miała wezwanie Świętych Dziesięciu Tysięcy Rycerzy Męczenników, odbyła się przed 1591 r. Ale już w tym roku kościół wymagał gruntownego remontu, którego podjął się ks. Walentyn Brokowski (1584 - ok. 1591). W 1704 r., w czasie przejścia wojsk szwedzkich, idących z Węgrowa do Kamieńczyka nad Bugiem, kościół uległ zniszczeniu.
Trzecią, modrzewiową świątynię w Kamionnie - za czasów ks. Stanisława Mościckiego (prob. 1671-1709) - ufundował w 1704 r. właściciel dóbr Kamionna - Stanisław Godlewski h. Gozdawa (zm. 1709), starosta nurski (1688-1709) i kasztelan podlaski (1705-1709). Po jego śmierci prace kontynuował jego brat - Jan Stanisław Godlewski (zm. 1717), stolnik (1689-1710) i podkomorzy nurski (1710-1717). Konsekracji kościoła pw. Świętych Dziesięciu Tysięcy Rycerzy Męczenników dokonał 1 lipca 1739 r. Marcin Załuski (1700-1768), biskup tytularny Drasus (1732), sufragan płocki (1732-1765). W latach 1865-1866 został przeprowadzony gruntowny remont świątyni pod kierunkiem ks. Józefa Wiktora (1829-1882), proboszcza w Kamionnie (1857-1882).
Obecny murowany kościół, w stylu neogotyckim, pw. Niepokalanego Poczęcia Najświętszej Maryi Panny, został zbudowany w latach 1904-1909 według projektu Józefa Piusa Dziekońskiego (1844-1927), staraniem ks. Antoniego Dzikowskiego (1859-1938), ówczesnego proboszcza w Kamionnie (1894-1920) oraz przy pomocy dziedzica Łochowa - Zdzisława hr. Zamoyskiego (1842-1925), właściciela klucza jadowskiego i kołodziążskiego oraz jego żony Marii ze Szwykowskich. Aktu poświęcenia dokonał 22 czerwca 1909 r. wspomniany ks. Antoni Dzikowski za pozwoleniem Konsystorza Warszawskiego.
W czasie I wojny światowej 8 sierpnia 1915 r. wojska rosyjskie wysadziły w powietrze dwie wieże, które padając, zniszczyły znaczną część świątyni. Przez kilka lat nabożeństwa były odprawiane w drewnianej kaplicy, urządzonej w domu parafialnym (1915-1921). W latach 1920-1923 funkcję proboszcza w Kamionnie pełnił ks. Michał Woźniak (1875-1942) - przyszły męczennik obozu koncentracyjnego w Dachau, wyniesiony do chwały ołtarzy 13 czerwca 1999 r. przez Ojca Świętego Jana Pawła II. Dzięki jego staraniom, pod kierunkiem inż. Adama Michalskiego, odbudowano fasadę kościoła. Prace te sfinalizował ks. Witold Lewicki (1888-1966), proboszcz Kamionny (1923-1966). Odrestaurowana świątynia została konsekrowana 16 maja 1927 r. przez ks. Henryka Przeździeckiego (1875-1939), biskupa siedleckiego, czyli podlaskiego (1918-1939). Mocą konstytucji apostolskiej Vixdum Poloniae unitas z 28 października 1925 r. parafia Kamionna przeszła z archidiecezji warszawskiej do diecezji siedleckiej, czyli podlaskiej.
W czasie wojny (23 listopada 1941 r.) kościół stracił dwa dzwony i doznał wielu szkód w czasie przechodzenia frontu (11-21 sierpnia 1944 r.). Staraniem kolejnych proboszczów: wspomnianego ks. Władysława Lewickiego i ks. Henryka Bujnika (1966--1982) uzupełniono wyposażenie świątyni.
W 1991 r. ks. Jan Kazimierczuk (ur. 1937), proboszcz w Kamionnie w latach 1982-1991, zmienił dach nad prezbiterium. W 1995 r., staraniem ks. Stanisława Grochowskiego (prob. 1991-1995) i jego następcy ks. Marka Bielaka, cały dach kościoła został odremontowany.
Warto zaznaczyć, że z parafii Kamionna pochodził ks. Michał Godlewski (1872-1956) - syn miejscowego dziedzica Antoniego Godlewskiego (1826-1899). W latach 1904-1926 był on wykładowcą historii w petersburskiej Akademii Duchownej, a w latach 1927-1949 na Uniwersytecie Jagiellońskim w Krakowie. 21 października 1916 r. został mianowany biskupem tytularnym Agbia i sufraganem łucko-żytomierskim (1917-1926). 14 stycznia 1949 r. został mianowany arcybiskupem tytularnym Amorianus.
Obok kościoła, po przeciwnej stronie ulicy, stoi murowana plebania zbudowana w latach 1922-1923 przez bł. ks. Michała Woźniaka. Jej projekt - autorstwa arch. Józefa Piusa Dziekońskiego - powstał w 1910 r., za czasów ks. Antoniego Dzikowskiego (1894-1920). Budowa plebanii została zakończona w latach 1923-1924 przez ks. Władysława Witolda Lewickiego (prob. 1923-1966).

Kaplice:
Łochów Fabryczny - kaplica dojazdowa (dawniej: Tartak Baczkowski, a później Baczki Fabryczne) swymi początkami sięga II wojny światowej, kiedy
1 marca 1942 r. otwarto i poświęcono tutaj Tymczasowy Szpital Epidemiczny. Wraz z likwidacją szpitala przestała istnieć kaplica. Obecna, pw. bł. Jadwigi Królowej, została zbudowana w latach 1983-1985 staraniem wspomnianego ks. Jana Kazimierczuka. Jej poświęcenia dokonał 15 sierpnia 1988 r. Jan Mazur, biskup siedlecki czyli podlaski (1968-1996) w ramach obchodów 500-lecia istnienia parafii.

Porządek Mszy św.:
- niedziele i święta:
- kościół parafialny: 9.00, 12.00, 17.00 (zima: 16.00)
- kaplica w Łochowie Fabrycznym: 10.30 (wakacje: 8.00)
- święta niebędące dniami wolnymi od pracy:
- kościół parafialny: 9.00, 17.00
- kaplica w Łochowie Fabrycznym: 18.00
Odpust w parafii: Niepokalane Poczęcie Najświętszej Maryi Panny - 8 grudnia, Dziesięciu Tysięcy Męczenników - 22 czerwca.
Nabożeństwo adoracyjne: przed Niepokalanym Poczęciem Najświętszej Maryi Panny - 6-8 grudnia.
Księgi metrykalne: Księgi Chrztów: od 1743 r.; Księgi Małżeństw: fragmenty 1629-1631; od 1645 r. (brak 1743-1745); Księgi Zmarłych: od 1647 r. (brak 1656-1746)

Bibliografia:
Archiwum Diecezjalne w Drohiczynie. III /Q/. Akta parafii Kamionna 1818-1921; 1925-1939; 1922-1982; 1955-1965; 1984; P. Aleksandrowicz, Diecezja siedlecka czyli podlaska, Sadowne 1956; Z. Czumaj, Dzieje parafii Kamionna koło Węgrowa w latach 1488-1945, Warszawa 2001 (mps); I. Galicka, H. Sygietyńska, Województwo Warszawskie. Powiat Węgrowski (Katalog Zabytków Sztuki w Polsce, t. X z. 26), Warszawa 1962; Katalog kościołów i duchowieństwa Diecezji Siedleckiej czyli Podlaskiej na rok 1929, Siedlce 1929; S. Ulaczyk (oprac.), Rocznik Diecezji Drohiczyńskiej. Spis parafii i duchowieństwa 1999, Drohiczyn 1999; T. Zasłona, Bł. Ks. Michał Woźniak w dziejach parafii Kamionna, Niedziela Podlaska nr 44 (2001) 5/320, s. III.