17 czerwca 1934 r. kamień węgielny pod budowę poświęcił arcybiskup gnieźnieński Antoni Laubitz. Kosztem 10 tys. złotych wybudowano w ciągu 3 lat świątynię według projektu Stefana CybichowskiegoWysocka Agnieszka: Kościoły projektu Stefana Cybichowskiego w Bydgoszczy i okolicach miasta. [w.] Kronika Bydgoska XXX 2008. Towarzystwo Miłośników Miasta Bydgoszczy. Bydgoszcz 2009. ISSN 0454-5451.
Konsekracji kościoła dokonał kard. August Hlond 15 maja 1938 r. Podczas uroczystości, we wnętrzu umieszczono figurę św. Wojciecha, a jedna z bocznych kaplic otrzymała wezwanie Matki Bożej Królowej Korony Polskiej. W latach 1936–1938 wzniesiono przy kościele plebanię według projektu bydgoskiego architekta Jana Kossowskiego w stylu tzw. dworkowym, popularnym w okresie międzywojennym.
W czasie II wojny światowej władze hitlerowskie odebrały świątynię katolikom i przekazały w użytkowanie ewangelikom. W końcu wojny kościół został uszkodzony, m.in. zbito wszystkie szyby, zniszczono w większej części okna oraz dach. Podobnie plebania, zbudowana w 1936 roku ucierpiała wskutek działań wojennych i zakwaterowania wojskaParafia pw. Najświętszej Marii Panny Królowej Polski w Brzozie. [w:] Myszka Łukasz: Gmina Nowa Wieś Wielka. Z dziejów samorządu terytorialnego do 2002 roku. . Bydgoszcz 2006.