Pierwszy kościół ewangelicko-augsburski w Olecku wzniesiono około 1560 r., wkrótce po nadaniu praw miejskich Margrabowej (tak wówczas nazywano Olecko). Kościół stał na niewielkim wzniesieniu, zwanym Wzgórzem Kościelnym. Tuż przy kościele, wewnątrz dziedzińca, znajdował się cmentarz.
Kościół w Margrabowej płonął wielokrotnie. Przed najazdem Tatarów w 1656 r. spalił się całkowicie, podobnie jak miejscowy ratusz. Odbudowany, spłonął ponownie 22 sierpnia 1684 r. Każdorazowo odbudowywano go dużym wysiłkiem tutejszej parafii ewangelickiej.
Pod koniec XIX w. Kościół poddano gruntownej renowacji, którą przeprowadzono w latach 1900/1901. W 1945 r. został całkowicie zniszczony przez wojska sowieckie.
Przez dziesiątki lat było to puste miejsce. Potem zamienione na plac zabaw dla dzieci z pobliskiego przedszkola.
24 września 1981 r. rozpoczęto budowę nowej świątyni pod wezwaniem Najświętszej Marii Panny Królowej Polski na podstawie projektu architektów A. Nowakowskiego i J. Pawłowskiego. 2 października 1984 r. wmurowano kamień węgielny, a konsekrowano 8 września 1990 r.
Kościół jest pomnikiem wdzięczności Bogu i Matce Bożej Królowej Polski za ocalenie Jana Pawła II.
Grafika z projektu www.egoturystyka.pl.
