Kamień węgielny pod budowę kościoła poświecono 4 maja 1913 r. Budowa świątyni wiązała się z rosnącą liczbą pruskiego garnizonu wojskowego w Olsztynie.
Ponieważ używany do dziś przez olsztyńskich ewangelików kościół Chrystusa Zbawiciela był za mały parafia porozumiała się z władzami wojskowymi i kościół był użytkowany nie tylko przez duszpasterstwo wojskowe, ale i świeckie.
Organy wybudowane przez firmę organmistrzowską Witteka z Elbląga w 1914 roku, uważane były przed II wojną światową za najlepsze w Prusach Wschodnich.
Ostatnie nabożeństwo ewangelickie odprawiono w 1945 roku. Później kościół przejęło Wojsko Polskie. Do 2014 roku parafia pełniła funkcję parafii garnizonowej, obecnie wchodzi w skład Archidiecezji Warmińskiej
Kościół zaprojektował berliński architekt Ludwig Dihm.