Фарны касцёл быў закладзены ў 1395 годзе Вітаўтам на месцы былога паганскага капішча. Першапачаткова касцёл быў асвечаны ў гонар Усіх Святых. У 1422 годзе Ягайла бярэ шлюб тут са сваёй апошняй (чацвёртай) жонкай Соф'яй Гальшанскай, родапачынальніцай дынастыі Ягелонаў. У гонар 600-годдзя з дня нараджэння Соф'і побач з храмам была высаджана лістоўніца, а побач устаноўлены памятны камень. 

У 1643 годзе на замову наваградскага кашталяна Яна Рудаміны ў храме ўсталёўваецца мармуровы барэльеф у памяць аб наваградскіх рыцарах, якія загінулі ў бітве з туркамі пад Хоцінам (1621). У 1712—1740 гадах праводзілася перабудова касцёла. 14 ліпеня 1714 года каад'ютарам віленскага біскупа Мацеем Анцутам быў асвечаны краевугольны камень перабудаванага касцёла. Вядома, што перабудовай займаліся мясцовыя будаўнікі-муляры: Якуб Бокша, Юрый Урлоўскі, Андрэй Шарэцкі, Юрый Стапкоўскі.

1723 г. касцёл асвечаны пад новай назвай «Божага Цела», але будаўнічыя работы працягваліся да 1740 года. Уяўляў сабой аднанефную базіліку з паўкруглай апсідай і дзвюма вежамі на галоўным фасадзе. У кампазіцыю касцёла былі ўключаны дзве гранёныя капліцы ранейшага гатычнага касцёла XIV—XV стагоддзяў. 

У 1776 г. біскуп Жулкоўскі асвячае касцёл у гонар «Прэабражэння Гасподняга». У гэтым храме 12 лютага 1799 года быў ахрышчаны сын Барбары і Мікалая Міцкевічаў, будучы знакаміты паэт Адам Міцкевіч. З гэтай нагоды ў 1920-я гады на сцяне касцёла, злева ад увахода, устаноўлена невялікая мармуровая таблічка. У 1812 годзе напалеонаўскія войскі, якія занялі горад, прыстасавалі старажытную царкву пад склад правіянту. Храм быў зачынены царскімі ўладамі пасля падаўлення паўстання ў 1864 годзе. Пазней храм пуставаў і прыходзіў у заняпад. Паводле інвентара 1867 года, быў крыты гонтам. У касцёле быў галоўны алтар, два бакавыя і два ў капліцах. Падлога была цагляная, пад ёй два, было вялікіх падвала. Вокнаў налічвалася сем і па два вокны ў капліцах. З левага боку ад прастола была рызніца з адным акном. 

Храм вернуты католікам у 1906 годзе. Аднаўленне святыні праводзілася толькі з 1921—1923 год, дзякуючы намаганням князя Станіслава Радзівіла і архітэктара Бейла. У 1922 г. біскуп Зігмунд Лазінскі на Дзень Усіх Святых нанова асвяціў касцёл. Парафія афіцыйна адрадзілася ў 1929 годзе, а святыня была аддадзена пад апеку сясцёр назарэтанак. У 1921—1922 гадах у храме служыў айцец Фабіян Абрантовіч. У 1922 годзе касцёл стаў пракафедральным саборам Мінскай епархіі. У 1920-я гады на сцяне старажытнага гатычнага касцёла, уключанага ў сучасны храм у выглядзе капліцы, умуравалі табліцу на памяць аб шлюбе ў 1422 годзе караля польскага і вялікага князя літоўскага Ягайлы з князёўнай Соф'яй Гальшанскай.

Падчас нацысцкай акупацыі ў Наваградку манашкі-назарэтанкі арганізавалі па просьбе бацькоў  падпольнае навучанне польскай мове і гісторыі. Падпольная школа спыніла існаванне пасля таго, як 1 жніўня 1943 года гестапаўцы пакаралі смерцю 11 манашак (наваградскіх пакутніц), у тым ліку галоўнага арганізатара школы. Ігумення манастыра сястра Адэля Мардасевіч (Марыя Стэла) звярнулася да нямецкіх уладаў з просьбай адпусціць арыштаваных, замяніўшы іх сабой, каб выратаваць жыцці 120 наваградчан і святара Зянкевіча схопленых нацыстамі і прыгавораных да смяротнага пакарання. Зараз мошчы прылічаных Святым пасадам у 2000 годзе да ліку блажэнных сясцёр у храме, а на месцы іх пахавання побач з храмам устаноўлена стэла. Іх імёны: Адэля Мардасевіч (сястра Марыя Стэла), Ядвіга Караліна Жак (сястра Марыя Імельда), Ганна Какаловіч (сястра Марыя Раймунда), Юзэфа Хробат (сястра Марыя Канута), Хелена Чэрпка (сястра Марыя Гвідана), Элеанора Анэля Юзьві Даніэля), Юлія Рапей (сястра Марыя Сергія), Яўгенія Мацкевіч (сястра Марыя Канізія), Паўліна Баравік (сястра Марыя Феліцыта), Леакадзія Матушэўская (сястра Марыя Геліядора), Вераніка Нармантовіч (сястра Марыя Барамея).

У 1948 годзе савецкія ўлады зноў закрываюць касцёл. У 1984—1998 гадах пробашчам парафіі быў прызначаны ксёндз Антоній Дзям'янка. Пры ім у 1992 годзе касцёл вяртаюць вернікам. У 1997 годзе адбывалася рэстаўрацыя храма. У 2006 годзе пробашчам з'яўляўся айцец Аляксандр Баклажак, а ў 2007 годзе яго змяніў айцец Ян Балтрукевіч.