Parafia powstała w 1504 r. z fundacji króla Aleksandra Jagiellończyka. Obejmowała rozległy obszar, który stopniowo uszczupliło powstanie sąsiednich parafii w Kuźnicy (1545), Lipsku (1582), Dąbrowie (1595), Zalesiu (1602) i Sidrze (1704). W 1536 r. prawa do Nowego Dworu wykupiła królowa Bona. Podniosła ona osadę do rangi miasta, a także dokumentem wydanym 1 sierpnia 1547 r. powiększyła uposażenie parafii o kolejne place i łąki. W 1580 r. król Stefan Batory nadał parafii karczmę.
Pierwszy kościół zbudował fundator parafii, król Aleksander. Nie wiadomo, jak pierwotnie wyglądała ta świątynia. Dopiero źródła XVII-wieczne informują, że prezbiterium i zakrystia kościoła były murowane, natomiast korpus nawowy wzniesiono z drewna. Na pokrytym gontami dachu znajdowała się niewielka sygnaturka. Po remoncie kościoła przeprowadzonym po 1674 r. bp sufragan wileński, Mikołaj Słupski konsekrował go 10 sierpnia 1679 r. podczas wizytacji.
W 1584 r. proboszcz, ks. Wojciech Krzyczkowski, ufundował altarię pw. Przemienienia Pańskiego przy nowodworskim kościele. W 1615 r. na potrzeby altarii świątynię powiększono o murowaną kaplicę, w której pochowano fundatora. Drugą, drewnianą kaplicę – altarię pw. Ukazania się św. Michała Archanioła – zbudował proboszcz, ks. Władysław Koc w 1703 r. Altarzyści otrzymali od donatorów odpowiednie uposażenie.
W połowie XIX w. kościół w Nowym Dworze był zrujnowany. Parafianie rozpoczęli starania o jego poszerzenie i podwyższenie. Jednym z inicjatorów przedsięwzięcia był Kazimierz Eynarowicz, właściciel pobliskiego majątku Kudrawka. Wierni zebrali ofiary pieniężne, dostarczyli materiały i zapewnili siłę roboczą. W 1877 r. rozpoczęto prace budowlane, kontynuowane jeszcze w latach 80. XIX w. Pozostawiono i podwyższono murowane prezbiterium, zakrystię i kaplicę Przemienienia Pańskiego. Drewniany korpus nawowy rozebrano i wzniesiono nowy z kamienia polnego. W efekcie powstała trójnawowa, eklektyczna świątynia z elementami neogotyku, o dwóch wieżach flankujących fasadę.
W latach 20. XX w. proboszcz, ks. Józef Lipiński przeprowadził remont kościoła po zniszczeniach powstałych podczas I wojny światowej. Świątynia została otynkowana, a na osi lewej nawy dobudowano drugą zakrystię. W tym czasie powstały też nowe ołtarze, a ołtarz Przemienienia Pańskiego przeniesiono do nawy bocznej. Rodziny Tomaszewskich i Łajkowskich ufundowały trzy dzwony.
Po II wojnie światowej, w wyniku wytyczenia nowych granic międzypaństwowych, część miejscowości należących do parafii w Nowym Dworze znalazła się na terytorium Białoruskiej Socjalistycznej Republiki Sowieckiej. Nowodworską parafię uszczupliła terytorialnie także erygowana w 1946 r. parafia w Siderce.
W latach 1981-1987 kolejny gruntowny remont kościoła, plebanii i budynków gospodarczych przeprowadził ks. proboszcz Zenon Siwicki. Wówczas, w latach 1985-1986, ponownie otynkowano świątynię. W 1995 r. została ona wpisana do rejestru zabytków. Przed jubileuszem 500-lecia parafii, który świętowano 24 czerwca 2004 r., pewne prace restauracyjne przy kościele i w jego otoczeniu wykonał proboszcz, ks. Jan Trochim.