Według legendy kościół na Piasku został ufundowany przez Władysława Hermana w 1087 roku, jako wotum za cudowne uzdrowienie. O legendzie tej wspomina w swym dziele Ogród fiołkowy karmelitański z 1637 roku Mikołaj Grodziński, którego praca utrwaliła przekonanie o starożytności kościoła. Legendy tej nie znał Jan Długosz, który w XV wieku napisał Księgę uposażeń diecezji krakowskiej. W dziele tym Długosz nie wspomina o powstaniu kościoła na Piasku i rzekomej fundacji Władysława Hermana. Zawierająca tyle szczegółów faktograficznych legenda, datująca początek kościoła na XI wiek powstała zapewne później niż dzieło Długosza. Źródło legendy należy wiązać z rozwojem kultu Matki Boskiej Piaskowej, któremu chciano przydać świetności.
W rzeczywistości fundacja kościoła i klasztoru wiąże się z końcem XIV wieku (1390) i osobami królowej Jadwigi i Władysława Jagiełły. Kościół pod wezwaniem Nawiedzenia Najświętszej Marii Panny oddany został w 1397 roku zakonowi Karmelitów, sprowadzonemu z Pragi. W tym czasie kościół nie był jeszcze ukończony. Gotowe były prezbiterium i zakrystia, podczas gdy mury korpusu dokończono dopiero po roku 1473. Ukończony na przełomie XV i XVI wieku gotycki kościół Karmelitów był budowlą halową, trzynawową, z prezbiterium tej samej co nawy długości. W fasadzie znajdowało się główne wejście do kościoła. Drugie wejście znajdowało się od strony południowej. Obok tego wejścia około roku 1500 powstał obraz Matki Boskiej z Dzieciątkiem. Według przekazu o. Jacka Duracza W historii o dziwnie cudownym obrazie z 1610 roku, obraz wkrótce zasłynął licznymi cudami. Stosunkowo szybkie rozprzestrzenianie się kultu Matki Boskiej Piaskowej spowodowało konieczność stworzenia sanktuarium, które prawdopodobnie powstało na przełomie XV i XVI wieku. Za najstarszą pewną wiadomość historyczną o istnieniu kaplicy można uznać informację zawartą w relacji nuncjusza Erminiusza Valentiego z jego pobytu w Polsce w 1604 roku. Pisze on, że przy kościele Panny Maryi na Piasku, w pewnej kapliczce jest na murze obraz Najświętszej Panny, o którym powiadają niektórzy iż nie wiadomo kto go namalował, lecz jest o nim mniemanie, że się objawił cudownie… Ta pierwsza kaplica była niewielkich rozmiarów, podłużna, o formach późnogotyckich. Gotycki kościół Karmelitów został silnie uszkodzony w 1587 roku w czasie oblężenia Krakowa przez arcyksięcia Maksymiliana. Ze źródeł pisanych wiadomo, że kościół został częściowo zniszczony. W całości przetrwała natomiast kaplica Piaskowa, a cudowny wizerunek pozostał nietknięty, co uznano za cud. W rok później przystąpiono do odbudowy zniszczonego kościoła. Zyskał on formę budowli o krótkim, jednoprzęsłowym i prostokątnie zakończonym prezbiterium. Od strony zachodniej zamykała go dwupiętrowa fasada, dachy natomiast pokryte były dachówką. W tym stanie kościół przetrwał do potopu szwedzkiego.
Rozkwit kultu Maryjnego w 1 połowie XVII wieku oraz pomyślna sytuacja ekonomiczna klasztoru piaskowego były czynnikami, które wpłynęły na decyzję budowy nowej kaplicy Piaskowej, przerastającej swą skromną poprzedniczkę rozmiarem i bogactwem formy. W 1629 roku rada miejska udzieliła Karmelitom gruntu potrzebnego pod rozbudowę kaplicy, kosztem drogi publicznej, czyli dzisiejszej ulicy Garbarskiej. Budowa nowej kaplicy trwała około czterech lat – od roku 1637 do 1641, przy czym główne nasilenie robót budowlanych przypadło na lata 1638-1639. Nowa kaplica, podobnie jak wcześniejsza, otrzymała formę podłużną, co wynikało przede wszystkim ze szczególnego usytuowania Cudownego Obrazu na ścianie zewnętrznej południowego muru korpusu kościoła i stanowiącego z oczywistych względów, centralny element wnętrza. Dzięki księdze dochodów i wydatków klasztoru Piaskowego z lat 1637-1641 możemy dokładnie odtworzyć etapy budowy nowej kaplicy.
Prace rozpoczęto w jesieni 1637 roku od wykopania fundamentów, utwardzenia grząskiego gruntu (bliskość Rudawy) oraz zgromadzenia materiałów budowlanych. Jeszcze przed zimą gotowe były fundamenty i część murów, które zabezpieczono słomą. W ciągu zimy 1637/38 kontynuowano zakupy materiałów na dalszą budowę. Wiosną prace były prowadzone w bardzo szybkim tempie. Już na przełomie maja i czerwca rozpoczęto roboty przy konstruowaniu rusztowania dla zasklepienia kopuły, roboty kamieniarskie i wprawianie okien. Równocześnie rozpoczęto prace przy wyposażeniu kaplicy. Przez całe lato prowadzono prace budowlane i wykończeniowe. Zasadnicze prace ukończono we wrześniu. Roboty wykończeniowe ruszyły znów w styczniu 1639 roku i trwały do września, choć już nie tak intensywnie jak w roku poprzednim. Obejmują one budowę latarni kopuły, którą wznosi z kamienia pińczowskiego kamieniarz Sebastian oraz wprawianie drzwi żelaznych i krat. W kwietniu 1640 roku kontynuowano roboty przy zamknięciu kopuły nad centralną częścią kaplicy, m.in. wypłacono wówczas należność P. Dzianiemu od rysowania czapki na kopułę kapliczną. W lecie tego roku wprawiono już okna do latarni oraz zakupiono złoto na złocenie krzyża kaplicznego i gałki. Przez cały rok powtarzają się notatki o wydatkach na łamanie kamieni w Pińczowie, przeznaczonych zapewne na licowanie fasady. Jesienią 1640 roku prowadzono ostatnie prace budowlane związane z wykończeniem latarni kopuły oraz pokryciem dachów, na które zakupiono blachę miedzianą. Roboty murarskie zostały zakończone w początkach jesieni 1641 roku, bowiem z tego czasu pochodzą ostatnie notatki o wypłatach należności dla murarzy. Kaplica nie posiadała początkowo zespołu rzeźb zdobiących obecnie kopułę i szczyty elewacji bocznych, pierwotnie zwieńczonych żelaznymi krzyżami, o czym świadczą zapisy w księdze rachunkowej.
Okupacja Krakowa przez wojska szwedzkie w latach 1655-1657, działania wojenne oraz strategiczne niszczenie przedmieść spowodowały znaczne zniszczenia klasztoru i kościoła Piaskowego. Ich zakres ze względu na brak danych archiwalnych jest trudny do ustalenia. Krótkie wzmianki zawarte w materiałach źródłowych oraz pochodzące z publikacji z 2 połowy XVII wieku sugerują całkowite zniszczenie kaplicy Piaskowej, podobnie jak i kościoła oraz klasztoru. Wydaje się jednak, iż przekazy te są mocno przesadzone. Gdyby rzeczywiście tak było odbudowa kaplicy miałaby charakter ścisłej rekonstrukcji pierwowzoru. Odbudowa kaplicy ze zniszczeń trwała w latach 1657-1679. Funduszu na ten cel udzielił biskup Piotr Gembicki. W 1678 roku umieszczono na szczycie kopuły brązową pozłacaną figurę Matki Boskiej z Dzieciątkiem wykonaną przez złotnika Mikołaja Truszowicza według drewnianego modelu autorstwa Kazimierza Kaliskiego. Zapewne w tym samym czasie w narożach ustawiono kamienne posągi świętych karmelitańskich, a na szczytach elewacji bocznych figury aniołów, które wymienia inwentarz z 1874 roku.
Gruntowna odnowa zewnętrznej architektury kaplicy miała miejsce w latach 50. XVIII wieku, o czym świadczy zapis na dokumencie z 17 maja 1757 roku znaleziony w gałce pod figurą Matki Boskiej wieńczącej kopułę. Niestety zakres prac nie jest znany. W wieku XIX kaplica była dwukrotnie odnawiana.
Pierwszą restaurację przeprowadzono od września 1851 roku do lutego 1852 roku z funduszy osób prywatnych. Na zewnątrz prace objęły przede wszystkim naprawę dachu, którego w tym czasie części boczne były pokryte dachówką, zaś kopuła blachą. Między rokiem 1851 a 1874 musiano prowadzić prace przy dachu kaplicy, bowiem inwentarz z 1874 roku podaje, iż kopuła pokryta była blachą miedzianą, a części boczne blachą cynkową.
Kolejne prace restauracyjne wykonane w ramach generalnej odnowy kościoła i klasztoru przeprowadzono w 1889 roku. Naprawiono wówczas dach kaplicy, a Józef Maszczyński odczyścił i wyzłocił na nowo figurę Matki Boskiej na szczycie kopuły.Druga gruntowna XIX-wieczna restauracja miała miejsce w 1898 roku, jednak nie wiadomo w jakim stopniu dotyczyła ona strony zewnętrznej kaplicy. Głównie na wnętrzu skupiły się także dwie XX-wieczne restauracje – w latach 50. oraz w 1982 roku. Prawdopodobnie w tym czasie odnawiano także elewacje zewnętrzne – prace ograniczyły się zapewne do odczyszczenia kamienia i pomalowania tynków.