Społeczność ukraińska jest w pewnym sensie nowością na mapie Warmii i Mazur, gdyż zasiedliła się tutaj w latach 40. XX w. Niestety Ukraińcy przybyli na te tereny nie z własnej woli. W roku 1947 zostali wyrwani siłą z terenów gdzie zamieszkiwali od wieków i w ramach akcji „Wisła” rozsiani po całym terenie kraju. Stosunkowo wielu z nich zostało osadzonych na małych wsiach obecnego województwa warmińsko-mazurskiego. Od samego początku byli oni szykanowani, prześladowani, traktowani jak obywatele niższej kategorii. W stosunku do nich zakazano używać określenia „Ukrainiec” na rzecz „wysiedleniec z akcji Wisła”. Władze komunistyczne powojennej Polski obarczyły tę społeczność balastem za czyny które popełniono w okresie wojny. Poddawani ustawicznym represjom i kampaniom propagandowym mającym na celu wzmożenie nastrojów anty-ukraińskich w społeczeństwie polskim mimo, że byli obecnie częścią tego regionu mieli być wymazani, skazani na asymilację, mieli zapomnieć skąd pochodzą i kim naprawdę są. Jednym z obowiązkowych punktów podczas przesiedlenia było to, że nie mogli mieszkać blisko większych miast i w jednej miejscowości nie mogło być ich więcej niż 10 %.
Cała ta sytuacja z oczywistych powodów nie sprzyjała rozwojowi życia duchowego wiernych grekokatolików, a przecież własna wiara jest jednym z bardzo ważnych czynników spajających społeczność, zwłaszcza gdy jest ona mniejszością. Mieli całkowity zakaz budowania własnych świątyń, próbowali więc zbierać się w kościołach katolickich, niestety pod czujnym okiem służb bezpieczeństwa i nie zawsze spotykali się z pomocną dłonią lokalnych proboszczów. Cała sytuacja zmieniła się pod koniec lat 50-tych, pozwolono utworzyć Ukraińskie Towarzystwo Społeczno – Kulturalne, nie zezwalano wybudować własnego kościóła, ale oficjalnie zezwolono na odprawianie greckokatolickich mszy w parafiach rzymskokatolickich.
Takim przykładem jest Dobre Miasto, gdzie od 1957 r. zaczęto regularnie odprawiać msze, tam też udawali się wierni z Olsztyna. W późniejszych latach, już w czasach odwilży, zaczęto adaptować nie wykorzystywane budynki sakralne, na potrzeby tworzących się parafii. Olsztyńska parafia greckokatolicka powstała dopiero w 1979 r. dzięki staraniom Prowincjała Zakonu Ojców Bazylianów o. Josafata Romanyka. Na początku lat 90-tych rozpoczęto starania o przekazanie obiektu nadającego się do adaptacji na świątynię, lub ewentualnie gruntu aby można ją wybudować. W rezultacie tych działań parafia otrzymała odpłatnie grunt na wieczyste użytkowanie przy ul. Lubelskiej. W 1994 r. rozpoczęto akcję zbierania pieniędzy na wykup terenu i na budowę świątyni, trzy lata później rozpoczęto prace. W roku 2000, Roku Jubileuszowym, w dzień odpustu Pokrowy Przenajświętszej Bogurodzicy, pod tym wezwaniem jest parafia, dokonano poświęcenia świątyni.
Cerkiew Pokrowy (Opieki) Matki Bożej jest piękną nowoczesną budowlą, posiada charakterystyczną dla stylu budownictwa cerkiewnego kopułę, a wewnątrz możemy podziwiać współczesny ikonostas. W 2003 r. rozpoczęto budowę wielofunkcyjnego domu parafialnego. Ten kto rozpoczyna przygodę z Olsztynem na Dworcu Głównym, nie może jej nie zauważyć, umiejscowiona jest dosłownie naprzeciwko. Miły akcent dla przybywających.