Kostel stojí na místě s dlouhou a proměnlivou historií. Původně zde byl městský hřbitov s malým kostelíkem. Po roce 1534, kdy panství po zemřelém Vojtěchu z Pernštejna přejal jeho bratr Jan, vznikl poblíž hřbitova první městský špitál. Původní kostelík však špitálním potřebám nestačil, a tak byl za držení města pány ze Stubenberku zbořen. Na jeho místě se začal stavět kostel nový a rozměrnější – a protože Stubenberkové byli luteráni, byl od počátku koncipován jako protestantský chrám. Výstavba se nicméně vlekla; teprve po deseti letech, roku 1597, byl kostel zaklenut.

Zlom přišel ke konci 17. století. Roku 1690 přistavěli novoměstští měšťané ke kostelu loretánskou kapli jako poděkování za to, že se mor, jenž tehdy řádil v Čechách, jejich městu vyhnul. Záhy nato, v roce 1692, tehdejší majitel panství Jakub Leslie při kostele zřídil obytnou budovu pro řád Milosrdných bratří, v níž měl fungovat špitál s deseti lůžky. První vikář s dvěma bratry dorazil z Vídně v roce 1696 a budova byla postupně přestavěna a rozšířena na konvent s lékárnou.

Jakmile byl konvent dokončen, ukázalo se, že starý kostel jeho potřebám nestačí. V roce 1757 se Milosrdní bratři rozhodli pro radikální řešení: kostel zbourali a vystavěli na témže místě chrám nový a větší. V letech 1767 až 1769 tak vznikl dnešní barokní kostel Narození Panny Marie, který tvoří páteř celého areálu.

Zvláštní pozornost si zaslouží loretánská kaple. Původně byla přistavěna roku 1680 ke staršímu hřbitovnímu kostelíku a po výstavbě nového kostela a věže byla začleněna do klášterního komplexu. Zachovala si přitom samostatný vstup z ulice skrze věž, a to v ose čelního portálu kaple. Tento raně barokní, pravoúhle profilovaný portál je završen piniovou šiškou uvnitř trojúhelníkového frontonu – detail, který stojí za povšimnutí. Vstup s letopočtem 1680 ve věži se přestal běžně využívat; kaple je dnes přístupná bočními vstupy, jež ji spojují s klášterním ambitem na jihu a s chodbou vedoucí k nemocnici na severu.

Mimo architektonické hodnoty přidává místu pozoruhodný kulturně-historický rozměr epizoda ze života Bedřicha Smetany. Skladatel jako mladík jezdíval za příbuznými do Nového Města nad Metují a 15. srpna 1840 – tehdy mu bylo šestnáct let – hrál při pouti v tomto kostele houslové sólo při mši svaté. Zpěvem ho doprovázela jeho sestřenice Louisa Smetanová, jeho první velká láska. Téhož roku pro ni složil svou proslulou Louisinu polku.

Areál kostela s konventem a loretánskou kaplí tak nabízí návštěvníkovi hned několik vrstev: staletý vývoj od hřbitovní kaple přes protestantský špitální chrám až po barokní klášterní komplex, drobný architektonický klenot v podobě portálu s piniovou šiškou a nečekaný osobní dotyk z dějin české hudby.