Der Legende zufolge steht der Standort der Kirche mit der Überbringung der Reliquien des Heiligen Florians nach Polen in Verbindung. Der Überlieferung nach blieben hier 1184 die Ochsen stehen, die den Wagen mit den sterblichen Überresten des Heiligen zogen, und wollten sich nicht mehr bewegen, bis man beschloss, an der Stelle eine dem Märtyrer geweihte Kirche zu errichten. Als diese gebaut wurde, war sie die wichtigste Kirche in Kleparz (damals noch einer selbständigen Stadt und dem heutigen Stadtteil von Kraków). Weitere Arbeiten fanden in den Jahren 1755-1779 statt, in denen neue Kapellen an der Westfassade angebaut wurden: Die Kapelle des Heiligkreuzes und der Schmerzensmutter, die Seitenaltäre und die Bestandteile der Innenausstattung. Im Chorraum befinden sich ein spätbarockes Gestühl mit Gemälden aus dem späten 18. Jahrhundert und der Hauptaltar mit der Darstellung des Heiligen Florian mit Ansicht von Kleparz im Hintergrund aus dem 17. Jahrhundert. In der Schatzkammer dieser Kirche wird ein gotischer Reliquienschrein in Form eines Türmchens aufbewahrt, der in der Schlacht von Tannenberg erbeutet und der Kirche von König Władysław Jagiełło geschenkt wurde. Dieser wurde 1365 für einen Komtur des deutschen Ordens angefertigt.

1999 erhob Papst Johannes Paul II. die Kirche in den Rang einer Basilika minor. Der spätere Papst Karol Wojtyła diente hier in den Jahren zwischen 1949 und 1951 als Vikar. Er wohnte damals im Pfarrhaus, gleich hinter der Kirche. Er machte sich in Kraków schnell einen Namen als akademischer Seelsorger, hervorragender Prediger und Beichtvater. In der St. Florian-Kirche organisierte er Gottesdienste für Kranke, Passionsandachten oder Weihnachtsliedersingen. 

Als Vikar organisierte er in der Kirchengemeinde zudem zahlreiche Ausflüge für Jugendliche, bei denen er Feldmessen feierte. Als Papst besuchte er seine ehemalige Kirchengemeinde nur ein einziges Mal, nämlich bei seiner letzten Pilgerreise in sein Heimatland 2002.

An seinen geistlichen Dienst in der Basilika erinnern heute zwei Gedenktafeln: eine im Inneren der Kirche und die andere am Pfarrhaus unter dem Fenster des Zimmers, in dem er wohnte.