Organizację prac związanych z tworzeniem nowej parafii kuria biskupia zleciła w 1936 r. ks. Emanuelowi Bonkowi. W grudniu 1937 r. powstał Komitet Budowy Kościoła dla dzielnicy „Hajduki-Dworzec” (pierwotna nazwa parafii NSPJ), który podjął decyzję by nowy kościół powstał pod wezwaniem Najświętszego Serca Pana Jezusa według projektu Henryka Gambca. Poświęcenia terenu i uroczystego, pierwszego wykopu ziemi dokonał 14 czerwca 1937 r. ks. bp Stanisław Adamski.
Poświęcenia kamienia węgielnego dokonał 14 sierpnia 1938 r. ks. dziekan Czempiel (jako delegat ks. bpa Ordynariusza Akt erekcyjny został wmurowany w kamień węgielny i umieszczony w ścianie za ołtarzem głównym). Mimo szeregu trudności zarówno finansowych jak również geologicznych (np. istnienie 3,5 m warstwy torfu) prace przy budowie świątyni postępowały na tyle szybko, że w sierpniu 1939 r. można było oglądać budynek kościoła w stanie surowym. Ze względu na ograniczone środki finansowe, początkowy projekt architektoniczny bryły kościoła, zaaprobowany przez kurię biskupią, uległ znacznym zmianom. Ostatecznie kościół przyjął prostą formę opartą na podstawowych bryłach z jedną wieżą. Wnętrze jest jednonawowe z wyróżnionym prezbiterium o kolebkowym sklepieniu i oddzielonym od dwóch ołtarzy bocznych kolumnami, po jednej z każdej strony.