Na początku XX wieku znaczna liczba żołnierzy stacjonujących w olsztyńskich koszarach była wyznania ewangelickiego. Wobec rozrastającego się garnizonu wojskowego koniecznością stała się budowa nowej świątyni. Jej wznoszenie rozpoczęto w 1913 roku, a do użytku oddano ją dwa lata później.
W zamyśle twórców kościół garnizonowy miał być miejscem nie tylko modlitwy i słuchania Słowa Bożego, ale też upamiętnienia żołnierzy garnizonu olsztyńskiego, którzy zginęli na frontach I Wojny Światowej. „Wchodząc do kościoła mieliśmy już tutaj spotkać się ze swoistym mauzoleum poświęconym żołnierzom. Miały tu znajdować się tablice upamiętniające żołnierzy olsztyńskiego garnizonu. Nie było głównych drzwi, one zostały wybite dopiero w latach czterdziestych, już po zakończeniu wojny. Boczne wejścia prowadziły do kościoła, a w miejscu obecnego wejścia głównego miało być rozbudowane pomieszczenie upamiętniające żołnierzy” - mówi ks. kan. dr Zbigniew Czernik, proboszcz parafii pw. Najświętszej Maryi Panny Królowej Polski i świętych archaniołów Michała, Rafała i Gabriela.
Do 1945 roku kościół służył ewangelikom zarówno cywilnym, jak i wojskowym. Z relacji miejscowej ludności dowiadujemy się, że odprawiano w nim również nabożeństwa katolickie. „W 1945 roku niemiecki kościół garnizonowy został przejęty przez Wojsko Polskie. W grudniu tego roku ówczesny administrator diecezji warmińskiej konsekrował kościół i przekazał kapelanom. I tu kapelani stanęli przed wyzwaniem, jak dostosować wnętrze poewangelickiego, garnizonowego kościoła do wymogów katolickich, do wymogów wojskowych, ale przecież też do wymogów socjalistycznych. Wojsko Polskie było socjalistyczne” - opowiada ks. Czernik. Kapelani w pierwszej kolejności usunęli wszystko, co kojarzyłoby się z niemieckością: herby, wizerunki postaci czy to, co jest charakterystyczne dla kościołów ewangelickich, jak chociażby empory wzdłuż ścian korpusu nawowego. „Jednym z takich głównych, interesujących przejawów tego dostosowywania wnętrza do wymogów wojska Polski Ludowej było namalowanie szeregu postaci świętych na ścianach korpusów w pasie okien kościoła. Pojawiają się tutaj postacie, 1958 rok, dwaj olsztyńscy malarze malują: Czesław Machnicki i Eugeniusz Kochanowski. Malują postacie świętych żołnierzy. To ma być to, co dla żołnierza Wojska Polskiego oprócz ewangelii ma budować jego morale. Ci święci żołnierze łączyli w swoim życiu chrześcijaństwo, wiarę w Chrystusa, ale wierną służbę ojczyźnie, wierną służbę jako żołnierze. Co ciekawe, wszystkie te postacie trzymają urny z prochami, gdzie w czasie II Wojny Światowej walczyli polscy żołnierze. Możemy tutaj dopatrzeć się zarówno miejsc walk na zachodzie Europy, jak również i na wschodzie. Stąd Lenino, stąd Dunkierka, stąd Warszawa, stąd Chełm, stąd szereg innych miejscowości istotnych dla działań Wojska Polskiego podczas II Wojny Światowej” - mówi ks. Czernik.
Wskutek reorganizacji olsztyńskiego wojska w 2009 roku parafia stała się wojskowo-cywilną. Od 1 stycznia 2014 jest już parafią cywilną pod wezwaniem Najświętszej Maryi Panny Królowej Polski i Świętych Archaniołów Michała, Gabriela i Rafała.
