Ulica Kościelna na Nowym Mieście ma ciekawą historię swego powstawania. Jej początki sięgają czasów lokacji Nowego Miasta. Po 1408 r. powstał tutaj kościół Nawiedzenia NMP wraz z towarzyszącymi mu zabudowaniami. Na odcinku przy kościele ukształtowała się krótka ulica, która przechodziła w ścieżkę prowadzącą do ulicy Rybaki. Natomiast odcinek leżący pomiędzy ulicami Przyrynek i Zakroczymską aż do 1868 r. stanowił część Rynku Nowego Miasta.
Pierwotną zabudowę arterii stanowiły drewniane domy, które dopiero w pierwszej połowie XVIII w. zaczęły zastępować murowane budynki. Pierwszymi takimi obiektami były Pałac Mokronowskich i nieduża kamienica. W XVIII w. ulicę zabudowano niewielkimi, skromnymi kamieniczkami. W 1770 r. Jakub Fontana na narożniku ulic Kościelnej i Zakroczymskiej zbudował dużą, bogato zdobioną kamienicę, a w 1776 r. Szymon Bogumił Zug Pałac Teofilii Dunin-Brzezińskiej, kupiony później przez Chodkiewiczów. W połowie XIX w. pojawiły się charakterystyczne drewniane schody prowadzące ku ulicy Rybaki.
Ze zniszczeń wojennych wiernie odbudowano kilka budynków, pozostałe są luźnym nawiązaniem do dawnego stylu tej części miasta. Uroczym miejscem ulicy Kościelnej są taras widokowy oraz drewniane schodki prowadzące do ulicy Rybaki i zespołu fontann multimedialnych.