Pierwotnie świątynia była pod wezwaniem świętego Idziego. W 1101 roku, biskup krakowski Lambert ustanowił przy kościele wspólnotę księży kanoników, czyli kolegiatę i właśnie wtedy po raz pierwszy pojawia się patrocinium świętego Andrzeja. Ówczesny kościół był usytuowany poza Krakowem, w osadzie nazywanej Okołem, która rozciągała się od ulicy poselskiej aż po wzgórze wawelskie. Była to jednonawowa bryła z wydłużonym prezbiterium zakończonym półkolistą absydą. Od zachodu fasadę wieńczyły dwie wieże z westwerkiem. To właśnie westwerk świadczy o możnowładczej fundacji świątyni. Westwerk jest rozwiązaniem architektonicznym, na który składają się wieże połączone emporą, czyli lożą. Miał on często charakter mieszkalny. Taki sposób budowy był powszechny w sakralnym budownictwie obronnym, szczególnie na terenie Cesarstwa, Czech i Siedmiogrodu.

Na przełomie XII i XIII wieku kościół został przebudowany. Tworzono trójnawową bazylikę, z pseudotranseptem oraz prezbiterium zamkniętym ścianą prostą. Nieznacznie podwyższono wieże, pozostawiono emporę do której dodano, zachowane do dziś, triforium czy romańskie, trójdzielne okno. Świątynia miała już stricte obronny charakter - była ufortyfikowana, otoczona wałem i fosą. Niewielkie okna znajdowały się jedynie w górnych kondygnacjach. Taki charakter budowli sprawdził się już w 1241 roku, podczas pierwszego najazdu Tatarów. Według relacji Długosza, w kościele ukryli się mieszkańcy i bronili swej osady, a sama świątynia była jedyną, która w pełni ocalała w czasie walk.

W 1316 roku, za sprawą małżonki Władysława Łokietka - Jadwigi Kaliskiej, do Krakowa zostały sprowadzone Klaryski, którym król, cztery lata później, oficjalnie ofiarował kościół świętego Andrzeja wraz z gruntami pod budowę klasztoru i zaplecza. Kolegiatę przeniesiono do pobliskiego kościoła świętego Idziego. W XV wieku kościół, dwukrotnie (1455, 1473), trawiły pożary, jednak budowla pozostała w niemalże w niezmienionym kształcie do dnia dzisiejszego.

W wieku XVI dobudowano od zachodu kościoła piętrowy budynek, który służył Pannom Klaryskom jako kostnica, kaplica i krypta. Dobudówka nie przetrwała do czasów dzisiejszych. W roku 1844 postanowiono poszerzyć ulicę Grodzką i tę część kościoła zburzono, mimo ostrego sprzeciwu zakonnic.

Największe zmiany i przekształcenia przyszły w XVII wieku. W roku 1639 podwyższono wieże, które nakryto barokowymi hełmami, zwiększono okna nawy głównej dla lepszego oświetlenia wnętrza. Przebudowa trwała od 1638 do 1707 roku, a prace nadzorował ksiądz Sebastian Piskorski, twórca jednego z najpiękniejszych kościołów barokowych - świętej Anny. Około1700 roku zmieniono wystrój wnętrza na barokowy. Dekorację stiukową wykonał Baltazar Fontana. Twórcą polichromii był prawdopodobnie malarz Karol Dankwart, choć istnieją sugestie, iż wykonał ją Innocenti Monti, obaj artyści współtworzyli w kościele świętej Anny. Pomysłodawcą wystroju ikonograficznego był sam ksiądz Piskorski, autor „Flores vitae Beatae Salomeae…” z 1691 roku. Powstała wtedy późnobarokowa, drewniana, ażurowa balustrada empory, zwieńczona misternymi elementami medalionów i wici roślinnych (1700 rok).

Kolejna faza przekształcania wnętrza kościoła nastąpiła, gdy ufundowano posadzkę z marmuru dębnickiego o dekoracyjnym układzie rombowym (1726 rok) oraz portal z prezbiterium do zakrystii, wzorowany na projekcie Andrea Pozzo. Natomiast nowy ołtarz z czarnego marmuru z obrazem świętego Andrzeja Apostoła, przypisany jest autorstwu Francesco Placidiego. Ostatnią fazę wyposażenia kościoła wiąże się z wykonaniem organów. Wykonał je dla klarysek organmistrz cysters Sitarski wraz ze współpracownikami. Ornament „rocaille”, zastosowany w formie stolarskiej dzieła datuje je na późne lata siedemdziesiąte XVIII wieku. Z tego okresu pochodzi także drewniana, częściowo złocona ambona w kształcie łodzi. Pokrewieństwo stylowe ze stolarką chóru i prospektu organów sugeruje rękę jednego snycerza. Pod koniec XVIII wieku sprawiono ołtarze boczne kościoła: Matki Boskiej Niepokalanie Poczętej, świętego Franciszka oraz świętej Klary.

Do kościoła przylega klasztor Panien Klarysek. Pierwotne zabudowania fundował król Łokietek, te niestety zniszczył pożar z 1455 roku. Nowe zostały postawione z sumptu Jana Długosza. Nowy, barokowy kształt nadano im z inicjatywy biskupa Bernarda Maciejowskiego i kardynała Jerzego Radziwiłła. Ten architektoniczny projekt przetrwał do roku 1844, kiedy to fasadzie budynku od ulicy Grodzkiej nadano neoromańskie formy nawiązujące do stylu samego kościoła.