Centrum dzisiejszego Nowego Miasteczka stanowi średniowieczny układ urbanistyczny, który stał się zalążkiem miasta. Rozplanowany w XIII wieku, składa się z prostokątnego rynku oraz siatki ulic wybiegających z niego ograniczonych dawniej miejskimi obwarowaniami. Na terenie tutejszej Starówki znajduje się najstarszy obiekt historyczny miasta.
Jest nim parafialny kościół św. Marii Magdaleny położony na zachód od Rynku. Warto przytoczyć trochę informacji o jego losach na przestrzeni ponad 700 lat istnienia Nowego Miasteczka.
Założycielem miasta nad Białą Wodą był najprawdopodobniej książę Henryk III Głogowski, który wspomina o jego istnieniu w swoim dokumencie z 1296 r. Z jego też inicjatywy powołano tutaj parafię katolicką. Dla wiernych wzniesiono pod koniec XIII wieku drewnianą świątynię istniejącą niespełna sto lat. W XIV wieku zastąpił ją jednonawowy, orientowany obiekt. Do nawy gotyckiego budynku dostawiono wieżę.
W XV wieku niewielki kościół przebudowano, aby pomieścić rosnącą liczbę wiernych. Już w XVI wieku nastąpiła kolejna modernizacja polegająca na dobudowie bocznej nawy połączonej z wieżą. Nowa część, jak i przebudowana wieża otrzymały wówczas renesansową formę. W tym samym okresie kościół przejęli nowomiasteczkowi luteranie, którym służył jako zbór w latach 1540-1634, do zniszczeń jakich doznał w czasie pożaru miasta.
Od ewangelików spalony budynek przejęli jezuici z Otynia, którzy stali się właścicielami miasta w 1649 r. Za ich sprawą świątynię odbudowano dodając elementy barokowe, zwłaszcza wyposażenie wnętrza. Świątynia przeszła ponowną konsekrację w 1702 r. otrzymując patronat św. Marii Magdaleny. Jezuici utracili świątynię w 1773 r., gdy ich zakon został skasowany decyzją władz pruskich.
Budynek należący od tego czasu do diecezji powiększono w pierwszej połowie XIX wieku o kruchtę. W tej formie gotycko-renesansowo-barokowa świątynia przetrwała do dziś. Po II wojnie światowej poddawano ją sukcesywnym remontom, a w ostatnim okresie przeprowadzono kompleksową renowację zarówno wnętrz, jak i elewacji oraz dachów.