Historia budowy kościoła sięga 1 stycznia 1991 roku, kiedy to erygowano parafię pw. św. Maksymiliana Marii Kolbego. W maju tego samego roku Państwowe Muzeum w Oświęcimiu przekazało parafii cegłę z krematorium celem wmurowania jej jako kamień węgielny pod świątynię. W sierpniu na Jasnej Górze kamień ten został poświęcony przez papieża Jana Pawła II. Jeszcze wcześniej, bo w czerwcu franciszkanie z Niepokalanowa przekazali parafii relikwię (włosy) św. Maksymiliana Marii Kolbego.
Budowa kościoła rozpoczęła się we wrześniu 1991 roku, a aktu wmurowania kamienia węgielnego dokonał w październiku tegoż roku ks. arcybiskup Jerzy Stroba. Pierwsza Msza święta odbyła się dnia 25 grudnia 1992 roku w murach budowanego kościoła - była to Pasterka. Od dnia 8 stycznia 1994 roku, tj. od 100-lecia urodzin patrona świątyni, Msze święte, chociaż z początku w prymitywnych warunkach, odbywają się w kościele. Do tego czasu przez okres 4,5 roku odprawiane były w kaplicy na cmentarzu parafialnym przy ulicy Kresowej.
Autorem projektu kościoła i kompleksu sakralnego była parafianka - architekt mgr inż. Ewa Winkowska, natomiast autorem wystroju wnętrza - artysta rzemieślnik Eugeniusz Olechowski z Poznania.