Ten dawny kościół ewangelicki to prawdopodobnie najwybitniejszy przykład sakralnej architektury protestanckiej na Warmii. Ta niezwykła budowla powstała w latach 1818 – 1823 i całe przedsięwzięcie zostało sfinansowane ze środków króla pruskiego Fryderyka Wilhelma III. Projekt tego dzieła wykonano w Berlinie w Wyższej Deputacji Budowlanej i jest bardzo śmiały jak na tamte czasy. Architekt zastosował tutaj idee łączenia historycznych form pochodzących z różnych epok i stylów w nowatorskie struktury pod względem kompozycji i estetyki.

Świątynia jest dwuwieżową, drewnianą konstrukcją ryglową na kamiennej podmurówce, oszalowana, posiada trzy nawy i płytkie prezbiterium od północy. Generalnie można ja nazwać pseudoromańska bazyliką emporową, podparta czworobocznymi słupami i otwarta do nawy głównej szerokimi półkolistymi arkadami.

Po zakończeniu działań wojennych, w skutek zawieruchy dziejowej z Lidzbarka zniknęli ewangelicy, kościół ewangelicki jako budynek przestał mieć racje bytu. W 1947 r. w ramach „Akcji Wisła” na teren ówczesnego województwa olsztyńskiego przesiedlono przymusowo 56 tysięcy Ukraińców, a wśród nich grekokatolików i prawosławnych. I to właśnie prawosławni otrzymali tę świątynię, bardzo szybko przystosowując ją do sprawowania liturgii wschodniej, usuwając dawne wyposażenie i umieszczając współczesny ikonostas. Dawna ewangelicka bazylika zmieniła się w prawosławną cerkiew pod wezwaniem Świętych Apostołów Piotra i Pawła, należącą do dekanatu Olsztyn i diecezji białostocko – gdańskiej Polskiego Autokefalicznego Kościoła Prawosławnego.

Cerkiew znajduje się przy ulicy Wysoka Brama, a 17 grudnia 1957 r. wpisana została do rejestru zabytków.