W 1731 r. na procesji Bożego Ciała przed kościołem nowomiejskim wystąpiła nadworna kapela złożona z samych murzynów. To historia jak najbardziej prawdziwa. Niemniej, trzeba mieć baczenie na fakt, że historiografii warszawskich kościołów towarzyszą liczne legendy i błędne przekonania. Jednym z najciekawszych przypadków jest właśnie gotycki kościół na skarpie. Jedni sądzą, że stoi w miejscu pogańskiej gontyny, inni że jest najstarszą świątynią Warszawy. Nic z tych rzeczy.
Minął rok od bitwy pod Grunwaldem, kiedy za murami Syreniego Grodu wystawiono gotycki kościół Nawiedzenia NMP. W tym czasie Nowe Miasto – najstarsze przedmieście Warszawy – intensywnie się rozbudowywało. Ludności nowomiejskiej także przybywało. Postarali się zatem książęta mazowieccy, aby dla każdego dostęp do ołtarza był jak najlepszy. Nie była w stanie kolegiata świętojańska pomieścić tak licznych wiernych z miasta i okolic, a na przykład ze wsi Polków droga do św. Jana była bardzo daleka.
O osobnej parafii, jak zapewnia Julian Bartoszewicz, zaczęła myśleć księżna Anna Mazowiecka. Przekazała pod budowę świątyni grunty. Darowiznę odpowiednim przywilejem zatwierdził książę Janusz. Budowa ruszyła, a działo się to najpewniej w roku 1409. „Wojciech Jastrzębiec biskup wydał potem stosowną erekcyją, sam zjechawszy na ten obrzęd do Warszawy, kościół poświęcił i rocznicę tej uroczystości na niedzielę po ś-tej Małgorzacie oznaczył” – pisał w 1855 r. monografista Bartoszewicz. Wkrótce obiekt zaczęto nazywać capella ducatis, czyli kościółek książęcy. Capella ducatis In civitate Nova Varsovia. Przez kolejne wieki kościół zmieniał swoje oblicze. Po przeszło 150 latach zyskał charakterystyczną wieżę. Z jej budową wiąże się legenda. Oto razu pewnego poczciwy nadwiślański młynarz zasnął, a we śnie objawiła mu się Najświętsza Panienka. Młynarzowi wiodło się nieźle. Zgromadził spory majątek, miał dobrą żonę. Niestety, próżno wyczekiwał potomstwa. Matka Zbawiciela obiecała zatem nieborakowi całą gromadkę, jeśli ten ruszy przed siebie, a na pierwszym napotkanym wzgórzu pokrytym śniegiem wzniesie kościół. Obudził się młynarz rano i nie tracąc czasu na zwłokę wyruszył. W końcu jego oczom ukazała się góra w śnieżnej czapce. Uradował się pobożny człek. Po chwili zorientował się jednak, że na szczycie już kościół kończą stawiać. Nie przejął się tym zbytnio i postanowił dobudować wysoką wieżę, spełniając tym samym przykazanie Maryi. Trudno wątpić, żeby wkrótce w domu młynarza nie rozległ się głośny śmiech płaczem i krzykiem przeplatany. Dzieci miał zapewne dwoje, troje, a może i pięcioro.
Zresztą, do dziś u podstawy wieży można zobaczyć świadectwo prawdziwości tej historii. Kamień młyński, który wmurowany jest w przyziemiu to pamiątka tamtych czasów. Tak przynajmniej powiadają starzy rybacy spod skarpy…
Kościół NMP wielokrotnie zmieniał swoje oblicze. Był też dwa razy rujnowany. Po raz pierwszy w czasie potopu szwedzkiego. Podobno po tej katastrofie nigdy już swojego dawnego blasku nie odzyskał. Po wtóre częściowo zburzony w czasie II wojny światowej. Obecny kształt nadano mu po wojnie, próbując odwzorować pierwotne, oryginalne rysy.