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. 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), trafiły pożary, jednak nie były to zniszczenia by kościół pozostał 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 r. 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 ks. Piskorski, autor „Flores vitae Beatae Salomeae…” z 1691 r. Powstała wtedy późnobarokowa, drewniana, ażurowa balustrada empory, zwieńczona misternymi elementami medalionów i wici roślinnych (1700 r.).

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 r.) oraz portal z prezbiterium do zakrystii, wzorowanym na projekcie Andrea Pozzo. Natomiast nowy ołtarz z czarnego marmuru z obrazem św. Andrzeja Apostoła , przypisany jest autorstwu Francesco Placidiego. Ostatnią fazę wyposażenia kościoła wiąże się z wykonaniem organów. Wykonał to 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 w. 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 w. sprawiono ołtarze boczne kościoła: Matki Boskiej Niepokalanie Poczętej, św. Franciszka oraz św. 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 nada no neoromańskie formy nawiązujące do stylu samego kościoła.