Pierwotny, gotycki kościół Nawiedzenia NMP (kościół Karmelitów na Piasku) wzniesiono w XV wieku. Całkowicie zniszczony podczas najazdu szwedzkiego (1655), został odbudowany w latach 1659-1679 w stylu barokowym i jest to do dziś ważny zabytek Krakowa. Opiekę duszpasterską w tym kościele sprawują ojcowie Karmelici.
Z kościołem tym związane są dwie legendy. Wedle jednej z nich księciu Władysławowi Hermanowi, cierpiącemu na schorzenie skórne przyśniła się Matka Boska wskazująca miejsce gdzie znajdzie fiołki. Książę miał kopać pod nimi aż znajdzie piasek, który go uzdrowił. Wdzięczny książę jest fundatorem bocznej kaplicy kościoła, w której znajduje się wizerunek Matki Boskiej, zwanej Piaskową. Okolica ta również nazywana jest Piasek.
Z kolei druga legenda opowiada o królowej Jadwidze, która wybrała się na spacer podczas budowy kościoła. Dostrzegła, ze jeden z budowniczych jest bardzo smutny. Zapytany o przyczynę powiedział, ze jego żona choruje, a nie stać ich na lekarstwo. Królowa Jadwiga oderwała złotą klamrę od pantofla uprzednio opierając stopę na kamieniu i ofiarowała drogocenny klejnot budowniczemu. Zdumieni robotnicy zauważyli, że w kamieniu odcisnął się ślad stopy królowej. Legendarny głaz został wmurowany miał zostać w ścianę kościoła.