Według mieszkańców dzielnicy miał on stanąć u zbiegu ulic Grodzkiej i Willowej, w okolicach zbudowanego po wojnie Zespołu Szkół nr 8.
thumb|Zaplecze kościoła W 1975 roku biskup Jan Zaręba zakupił działkę o powierzchni 769 m² przy ul. Krokusowej 9 (wówczas: Jeżynowa 9). Jej formalnym właścicielem był proboszcz parafii katedralnej ks. Jan Paweł Grajnert. W 1983 roku została przekazana notarialnie nowo powstałej parafii Najświętszej Maryi Panny Królowej Polski. Uznano jednak, że teren nie nadaje się na budowę kościoła, ponieważ jest zbyt mały i stromo położony. 6 stycznia 1987 parafia przekazała ją Zgromadzeniu Sióstr Westiarek Jezusa z przeznaczeniem na budowę domu zakonnego.
4 stycznia 1982 roku parafia nabyła działkę przy ul. Krokusowej 1/3 o powierzchni 66 arów i 70 m². Wkrótce powstała tam tymczasowa kaplica, poświęcona 1 sierpnia.
Zezwolenie na rozpoczęcie budowy kościoła wydano 4 lipca 1983 roku. Kamień węgielny pod budowę kościoła wmurowano 1 września 1985 roku. Został on wyjęty z bazyliki św. Piotra w Watykanie i poświęcony przez papieża Jana Pawła II, a wmurowany przez biskupa Jana Zarębę. Projekt kościoła stworzył inż. Jan Kopydłowski, a plany techniczne Józef Strzelecki.