Historia Obecny Park Lotników Polskich znajduje się na dawnych terenach fortecznych. Genezą kształtu obecnego parku jest lokalizacja na tym obszarze zbudowanego w latach 1864–1869 fortu reditowego 15 „Pszorna” i ustanowionych wokół niego stref ograniczeń budowlanych, które wytworzyły rezerwę terenową, na obszarze której później powstał park. Fort został rozebrany w 1951 roku w związku z rozbudową szlaku komunikacyjnego, który odtąd miał się stać główną arterią łączącą centrum Krakowa z budowaną Nową Hutą. Powstała dwujezdniowa droga z torowiskiem tramwajowym pomiędzy jezdniami – ówczesna aleja Planu 6-letniego, obecna aleja Jana Pawła II. Dotychczasowa droga omijała fort łukiem od strony południowej – obecnie śladem tym wiedzie jedna z parkowych alej. Równocześnie wyprostowano przebieg linii kolejowej nr 111 (Kraków Główny – Kocmyrzów), którą zlikwidowano na tym odcinku 20 lat później. Pozostałościami po forcie widocznymi do dzisiaj w krajobrazie parku są fragmenty stoków i murów przy alei Jana Pawła II, która przecina fort na pół.