Kościół powstał z fundacji króla Kazimierza Wielkiego. On też osadził w nim zakon Augustianów, który opiekuje się kościołem do dziś. Budowa gotyckiej bazyliki rozpoczęła się ok. 1343 roku. Niestety, nigdy nie została w pełni zakończona. Mówiono nawet, że nad świątynią zaciążyła klątwa, jaką nałożył na króla biskup Bodzanta za rzekomo rozwiązły tryb życia monarchy. Z tą niemiłą wieścią biskup wysłał wikarego katedry Marcina Baryczkę. Król w przypływie gniewu nakazał utopić posłańca. Kościół św.św. Katarzyny i Małgorzaty miał być jego ekspiacją za rozkaz zabicia wikarego.

Jednak konflikt między królem a biskupem miał w rzeczywistości głębsze podłoże, dotykające delikatnej materii stosunków między państwem a kościołem. Poselstwo wysłane do papieża Klemensa VI (1350 r.) dało w efekcie zdjęcie klątwy, jednak za cenę budowy szeregu kościołów. Tak oto biskupia anatema przysłużyła się pośrednio nie tylko krakowskiej, ale i polskiej architekturze sakralnej...

Początkowo budowa postępowała szybko i bez przeszkód. Jednak w roku 1443 wskutek trzęsienia ziemi runęło sklepienie prezbiterium. Ponieważ kataklizm nie wyrządził innych poważnych szkód, nasuwa to podejrzenia co do jakości pracy muratorów kościoła. Ta katastrofa zapoczątkowała lata niefortunnych dla kościoła wydarzeń. U progu XVI w. był już odbudowany, ale nie oszczędziły go kolejne kataklizmy: powódź (1534 r.) i pożar (1556 r.). Podczas najazdu szwedzkiego w świątyni i klasztorze urządzono szpital polowy, skład amunicji i stajnie. W grudniu 1786 roku w Krakowie znów zatrzęsła się ziemia i znów ucierpiał tylko kościół św. Katarzyny. Po trzecim zaborze (1796 r.), Austriacy zamknęli go definitywnie, przeznaczając go na magazyn wojskowy. Kiedy nadwątlone wstrząsami sklepienie nawy runęło ostatecznie (1826 r.), nad kościołem zawisła groźba wyburzenia. Jednak augustianie zdobyli fundusze na restaurację świątyni, którą rozpoczęto w połowie XIX w. i która trwa - z przerwami - do dziś.

Mimo tych perypetii kościół zachował swój szlachetny, gotycki charakter. Skromny wystrój wzbogaca późnorenesansowy nagrobek Spytka Jordana i barokowy ołtarz. Od południa przylega do kościoła kruchta z portalami o schodkowych zwieńczeniach, bogatą dekoracją maswerkową i kamiennymi laskowaniami. Kaplica św. Moniki, ze sklepieniem wspartym na ośmiobocznym filarze, służy jako oratorium siostrom augustiankom z domu zakonnego po drugiej stronie ulicy Skałecznej. Kryty ganek, który łączy budowle, jest malowniczym akcentem tej okolicy.

Od północy przylega do kościoła rozległy klasztor. W jego krużgankach można zobaczyć nieźle zachowane gotyckie malowidła ścienne (rzadkość!), kaplicę z namalowanym na ścianie wizerunkiem Matki Boskiej Pocieszenia oraz barokową kaplicę Izajasza Bonera, zwanego błogosławionym.