Projekt świątyni wykonał w 1909 berliński architekt Ludwig Dihm. Kamień węgielny pod budowę obiektu został jednak położony dopiero cztery lata później, 4 maja 1913. Plac, na którym miała powstać świątynia, przekazało wojsko - był to fragment dawnego placu ćwiczeń piechoty przy ul. Koszarowej (obecna ul. Kromera). Prace przy wznoszeniu obiektu wykonywały firma A. Pfeiffera (murarskie) oraz A. Lindermanna (dekarskie). Do marca 1914 wykonano drewnianą konstrukcję dwóch hełmów na wieży kościelnej. 4 lipca 1915 obiekt został oddany do użytku liturgicznego, chociaż trwały w nim jeszcze prace przy dekoracji wnętrza. W 1923 przed kościołem zostały ustawione dwa pomniki ku czci poległych w I wojnie światowej żołnierzy niemieckich: 146. pułku piechoty i 73. pułku artylerii polowej. Do 1945 kościół służył żołnierzom wyznania ewangelickiego. Gdy Olsztyn znalazł się w granicach Polski, świątynię przejął Kościół katolicki.