Tradycja wiąże powstanie kościoła z osobą króla Kazimierza Wielkiego. Ów władca miał się dopuścić haniebnego czynu zabicia księdza Marcina Baryczkę gdy ten napominał go za zbyt rozwiązły tryb życia. Na polecenie króla ciało księdza miało zostać wrzucone do Wisły, ta oddała zwłoki ksiedza nieco dalej, właśnie tu, gdzie dzisiaj stoi świątynia mająca być przeprosinami za popełnioną zbrodnię.
  Ile w tej legendzie prawdy? Co najwyżej imię fundatora - Kazimierza Wielkiego. Istotnie, kościół św. Katarzyny został zbudowany na polecenie króla jako jeden z obiektów większej całości, jaką jest po prostu miasto Kazimierz. W siedem lat po lokacji miasta, czyli w roku 1342 przybywa na zaproszenie władcy Szymon Sporer - pierwszy augustianin. Wtedy też rozpoczyna się budowa kaplicy św. Doroty oraz zapewne także drewniany zespół zabudowań dla nowego zakonu, stawianych na terenach darowanych przez króla znajdujących się między Skałką a rynkiem.
  Około 1363-65 roku rozpoczyna się budowa dzisiejszego kościoła. W wyniku prac trwających około 15 lat powstało wydłużone prezbiterium (konsekrowane w 1378), do roku 1428 zaś wybudowana została pozostała część świątyni oraz zabudowania klasztorne. Kościół św. Katarzyny nigdy jednak nie został ukończony. Od zachodniej strony widoczne są ślady wskazujące, że świątynia planowana było o jedno przęsło dłuższa. Od końca XV wieku kościół i klasztor ustrzegły się zmian poważnie ingerujących w kształt założenia, kolejne zmiany nastąpiły co najwyżej w wyniku wprowadzania form małej architektury.
  Do tychże małych form należą ołtarz główny, stalle, nagrobek Wawrzyńca Spytka Jordana, postać ukrzyżowanego Chrystusa w belce tęczowej oraz figura św. Rity. Ozdobą kościoła są także liczne obrazy oraz chór zakonny z organami.
  Na co zwrócić uwagę wchodząc do kościoła? W pierwszej kolejności warto zadrzeć głowę do góry. Na sklepieniu widoczny jest zarys desek - pierwotne gotyckie sklepienie kościoła nie przetrwało, w połowie XV wieku runęło, być może wskutek trzęsienia ziemi. Kolejne klęski, głównie pożary też nie oszczędziły świątyni. To, czego nie dokonała natura, dokonał człowiek. Po trzecim rozbiorze Polski i zajęciu Krakowa przez Austriaków w kościele urządzono magazyny wojskowe, na początku XIX wieku był tutaj skład słomy. Dopiero od 1814 roku, czyli od powrotu augustianów można było chociaż próbować przywrócić świątyni dawny splendor. W wyniku akcji zainicjowanej przez przeora Wincentego Gaździńskiego w pierwszej poł. XIX w. udało się zgromadzić środki na zrekonstruowanie drewnianego sklepienia remont ścian i okien. Kolejne prace konserwatorskie przypadają na koniec wieku XIX oraz okres międzywojenny. Kolejni restauratorzy świadomie podchodzili do obiektu, mimo prowadzonych prac nie starano się przeładować świątyni, zachowano i wyeksponowano piękne gotyckie wnętrze, którym zwiedzający Kraków i Kazimierz może się cieszyć po dzień dzisiejszy.
  Po prawej stronie świątyni, tuż przy wejściu do prezbiterium znajduje się figura świętej Rity z Cascii - patronki od spraw beznadziejnych. Figura wyrzeźbiona została przez Karola Muszkieta w 1929 roku. Według legendy:

Rita wyszła za mąż za mężczyznę butnego i agresywnego. Któregoś razu ów mężczyzna wdał się w bójkę, w wyniku której poniósł śmierć. Dwaj jego synowie postanowili pomścić ojca. Wówczas Rita poprosiła Boga, by Ten zrobił wszystko, by jej synowie nie popełnili zbrodni. Wkrótce obaj jej synowie zmarli a Rita wstąpiła do zakonu augustianek.

  Tuż przy figurze świętej Rity znajdują się jej relikwie. 22 dnia każdego miesiąca odbywa się w kościele nabożeństwo ku czci świętej Rity. Krakowianie tłumnie przychodzą na uroczystości, zostawiając czerwone róże.
  Tuż przy figurze św. Rity znajduje się nagrobek Wawrzyńca Spytka Jordana.
  Po lewej stronie kościoła zawieszony jest obraz autorstwa Izydora Jabłońskiego przedstawiającego św. Augustyna idącego wzdłuż plaży. Tematyka związana jest z legendą, wg której:

Święty Augustyn szedł wzdłuż plaży, rozmyślając czym jest Trójca Święta. W pewnym momencie zobaczył chłopca, który wykopał w piasku zagłębienie a przesiąkającą wodę wylewał do morza. W pewnym momencie chłopiec odwrócił sie w kierunku Augustyna i poważnym głosem rzekł: 'Prędzej ja przeleję tą wodę niż ty docieczesz, czym jest Trójca Święta'.

W ikonografii św. Augustyn przedstawiany jest najczęściej jako mężczyzna u boku którego siedzi chłopiec z muszelką przelewający wodę.