Pierwotna nazwa wsi brzmiała: Niemyje Siudy i pochodziła przypuszczalnie od mieszkańca tej wsi - Macieja Siudy Niemyjskiego (1567). Po raz pierwszy wieś ta została wymieniona w dokumencie z 1451 r. związanym z wytyczaniem granic. Przez wiele wieków Niemyje należały do parafii Winna Poświętna.
Inicjatorem utworzenia tutaj parafii był ks. Kazimierz Dymitrowicz (1890-1975), proboszcz parafii Winna Poświętna (1933-1945). Decyzja o budowie kościoła została podjęta na zebraniu 3 sierpnia 1947 r. w Niemyjach, któremu przewodniczył ks. Henryk Humnicki (1873-1959), wikariusz kapitulny diecezji pińskiej (1946-1950). W 1947 r. została zbudowana świetlica przyszkolna, w której urządzono dojazdową kaplicę. Wkrótce kaplicę przeniesiono do prywatnego domu Jana Niemyjskiego (1907-1971) prezesa Komitetu Budowy Kościoła, ponieważ władze szkolne zabroniły odprawiać nabożeństwa (1947-1949). W 1949 r. został zakupiony w Leopoldowie (diecezja siedlecka) drewniany poniemiecki barak, z którego zbudowano w listopadzie tegoż roku tymczasową kaplicę, kosztem ks. kan. Tadeusza Drozdowskiego (1909-1981), proboszcza parafii Leopoldów (1947-1953). Została ona postawiona na polu gospodarzy z Niemyj Jarnotów Stanisława Niemyjskiego (1913-1974) i Józefa Kryńskiego. Plac pozyskano 29 lipca 1949 r. drogą zamiany gruntów.
Parafia Niemyje Nowe została wydzielona z parafii Winna i erygowana z dniem 3 maja 1950 r. przez wspomnianego wikariusza kapitulnego ks. Henryka Humnickiego. Dekret wszedł w życie 22 października 1950 r. Pierwszym proboszczem został ks. Henryk Kardasz (1914-1995), dotychczasowy wikariusz w Winnej Poświętnej (1946-1950).
15 kwietnia 1952 r. drewnianą kaplicę przeniesiono na plac kościelny. Po jej rozbudowie została ona poświęcona przez ks. Henryka Kardasza, miejscowego proboszcza (1950-1957) 25 lipca 1954 r.
W październiku 1950 r. rozpoczęto budowę murowanej świątyni, według projektu inż. Bukowskiego i Stanisława Smacznego z Białegostoku. Plac pod nowy kościół pozyskano 27 grudnia 1949 r. - drogą zamiany z gruntami Władysława Kryńskiego. Poświęcenie kamienia węgielnego, którego dokonał ks. kan. Nikodem Kowalewski (1888-1974), dziekan ciechanowiecki (1934-1959), odbyło się 6 maja 1951 r. - na mocy delegacji ks. Michała Krzywickiego (1895-1967), administratora apostolskiego diecezji pińskiej (1950-1967). Prace przy wznoszeniu świątyni kontynuowali kolejni proboszczowie: ks. Adolf Kozłowski (prob. 1957-1959) i ks. Piotr Grzegorczuk (prob. 1959-1962). Poświęcenia nowego murowanego kościoła dokonał 22 października 1961 r. wspomniany administrator apostolski ks. inf. Michał Krzywicki. Uroczysta konsekracja odbyła się 29 sierpnia 1966 r., pod przewodnictwem bp. Władysława Jędruszuka (1918-1994), sufragana diecezji pińskiej (1963-1967).
Na placu przykościelnym stoi metalowa dzwonnica zbudowana w 1975 r. przez Romana Murawskiego z Ciechanowca, staraniem ks. Jana Komosy, proboszcza niemyjskiego (1971-1979).
W pobliżu kościoła znajduje się drewniana plebania, zbudowana w 1951 r., którą 28 października 1951 r. poświęcił ks. Marian Godlewski (1899-1964), proboszcz parafii Osmola (1935-1957).

Bibliografia: J. Smolarczuk, Zarys dziejów parafii Niemyje Nowe, Niemyje 1994 (mps).

Porządek Mszy św.:
- niedziele i święta:
- kościół parafialny: 9.00, 12.00
- święta nie będące dniami wolnymi od pracy:
- kościół parafialny: 10.00, 16.00

Odpusty w parafii: Matki Bożej Królowej Polski - 3 maja; św. Tadeusza - 28 października
Nabożeństwo adoracyjne: 26-28 października

Księgi metrykalne:
Księgi Chrztów: od 1950 r.
Księgi Małżeństw: od 1950 r.
Księgi Zmarłych: od 1950 r.