O samych początkach chrześcijaństwa na terenie dzisiejszego pogranicza śląsko-łużyckiego możemy powiedzieć tyle, że do krzewienia wiary w Jezusa Chrystusa na tych terenach bardzo mocno przyczyniła się księżna św. Jadwiga Śląska, a także zakony – w tym szczególnie zakon cysterski. O istnieniu ośrodka kultu religijnego, a konkretnie w Lubaniu, wspomina się już w połowie X wieku. O podobnym fakcie w Olszynie w tamtym okresie dziejów z dużą dozą prawdopodobieństwa mówi w swojej „Kurze Geschichte des Dorfes Langenöls nebst Kleinstöckigt und Gieshübel (1440 – 1859)” ewangelicki pastor i kronikarz dziejów Olszyny, Krzewia Małego i Grodnicy Oswald Kadelbach, opisując pierwszą budowlę jako niewielki, być może nawet murowany, budynek zwieńczony drewnianym dachem, na którego szczycie znajdowała się drewniana wieżyczka z sygnaturką.

Jednak wydaje się, że Olszyna w XIII i XIV wieku była dość ważną osadą, która służyła wtedy jako książęcy lub klasztorny folwark. Stąd właśnie pierwsza wzmianka o wsi, która w dokumentach pojawia się 6 listopada 1254 r. w kontekście kontraktu dzierżawnego między Zakonem Sióstr św. Marii Magdaleny z Nowogrodźca nad Kwisą a właścicielem Zamku Gryf – Wittigo de Greiffenstein. Tam właśnie Olszyna pojawia się jako „villa Olsne”.

Ta sama nazwa znajduje się w kronice, w której wspomina się, że książę legnicki Bolesław III Rozrzutny, zwany także Hojnym, w 1314 r. odsprzedał prawa patronatu nad majątkiem zwanym wtedy „villa Olsne”. Warto nadmienić, że Bolesław (Bolko) III był prapraprawnukiem księcia Henryka Pobożnego.

Po roku 1314 przez długi okres historii nie wiemy dokładnie, jak układały się dzieje wspólnoty katolickiej w Olszynie i jakie były losy kościoła. Na pewno wzmiankowany był w 1440 r. podczas podziału Olszyny.

Tragedią były wojny husyckie w l. 1426-27 oraz epidemia dżumy, która dziesiątkowała ludność, na piedestał wynosząc odwagę grabarza, któremu wystawiono nawet niewielki pomnik w niszy świątyni.

Dramatyczne czasy dla starego kościoła to także okres reformacji luterańskiej. Ówczesny proboszcz Olszyny ks. Vincenz Wonsch w aktach miasta Gryfowa Śląskiego już w 1520 r. wymieniany jest jako człowiek żonaty, luteranin. Za nim w 1523 r. poszła cała parafia, odłączając się tym samym od Kościoła rzymskiego. Świątynia parafialna stała się ewangelicka.

Przez 134 lata – aż do 6 kwietnia 1654 r. kościół był więc ewangelicki.

W 1567 r. miała miejsce pierwsza przebudowa kościoła, który powiększony został o gotycką zachodnią część. W 1614 r. powstał piękny strop kasetonowy z obrazami Jezusa Chrystusa, św. Jana Chrzciciela, Apostołów, Anioła Pokoju oraz roślinnymi ornamentami. Z tego samego okresu pochodził zapewne także chór organowy i po stronie południowej ambona, a także – nieco później – późnorenesansowa nastawa ołtarza głównego.

6 kwietnia 1654 r. nastąpił przełom. Po wojnie trzydziestoletniej olszyńska świątynia, na mocy pokoju westfalskiego, powróciła do rąk katolików i podporządkowana została duchownym z Kościelnika, a potem z Gryfowa Śląskiego.

W 1676 r. miała miejsce powtórna przebudowa kościoła.

W l. 1709-11 właściciel majątku zamkowego Abraham Ernst von Döbschütz postanowił wybudować wieżę dzwonniczą, która stała się także jego rodzinną kryptą grobową.

Akta wizytacyjne biskupów wrocławskich (XVII/XVIII wiek) wspominają też o pewnym cudownym zdarzeniu. Miało ono związek z figurą Pana Jezusa Frasobliwego z Ołtarza Oliwnego, kiedy to jeden z gryfowskich proboszczów – Bartholomäus Greger – w 1702 r. postanowił przenieść ją z Olszyny do Gryfowa. Według tych relacji, 10 kwietnia został rażony piorunem, czego świadkami było 8 innych osób będących wtedy w kościele. Szczęśliwie wyleczony, po 14 tygodniach mógł znowu sprawować swój urząd. Jednak piorun jeszcze trzy razy uderzał w to samo miejsce w kościele, co odczytano jako znak, że wspomniana figura powinna powrócić do kościoła w Olszynie.

Niestety, ludność katolicka była zbyt uboga i z wielkim trudem udawało się jej utrzymać swoją starą katolicką świątynię. 29 września1836 r. katolicka parafia w Olszynie straciła autonomię i stała się częścią parafii gryfowskiej (i tak pozostało aż do 1945 r.).

W 1896 r. na polecenie kard. Georga Koppa, biskupa wrocławskiego, wybudowano szkołę katolicką, w której naukę pobierało 45 dzieci.

W l. 1936-38 przeprowadzony został kapitalny remont kościoła, a wieża – użytkowana dotąd tylko przez ewangelików – stała się organiczną częścią świątyni. Renowacji poddano ołtarze (było ich cztery), sufit kasetonowy, wszystkie instalacje, a także elewację zewnętrzną. Konserwatorzy odkryli także unikatowe freski na wschodniej ścianie prezbiterium, przedstawiające Pietę i scenę Getsemani.

W 1937 r. wybudowano nowe 16-głosowe organy firmy Carla Berschdorfa z Nysy. W latach 30. XX wieku uzupełniono wyposażenie. Większość z tego istnieje do dziś.

Przeglądając inwentarz kościoła, sporządzony 4 czerwca 1943 r. przez ks. Augustina Hanke, ówczesnego gryfowskiego proboszcza, można odnieść wrażenie, że Kościół katolicki w Niemczech w trudnych czasach narodowego socjalizmu nabierał rozpędu, jakiego nie miał od czasów reformacji. Życie religijne cechowała głębia, wyrażająca się w procesjach, nabożeństwach i podczas Mszy św., które w Olszynie odprawiano tylko dwa razy w tygodniu – w niedziele i środy. Żywy był kult Matki Bożej (Himmelskönigin), której figurę w 1903 r. z St. Ortisei (Val Gardena) w Południowym Tyrolu sprowadził katolicki nauczyciel i kantor Hermann Scholz, a jego następca Fritz Schieb był nawet autorem specjalnej kompozycji mszalnej, która jednak zaginęła tuż po wojnie. Świadectwem tego ożywienia były remonty i nowe fundacje, którym kres położyła wojenna zawierucha i zmiany granic.

Po przyjściu Polaków nic nie miało być już takie samo. W lipcu 1946 r. proboszcz ks. Władysław Stefański przeniósł życie duchowe do kościoła poewangelickiego św. Józefa Oblubieńca NMP. Prawie całe wyposażenie poza Ołtarzem Oliwnym zostało przeniesione, a nowe organy wyjechały do Warszawy i dziś znajdują się w Kaplicy Literackiej archikatedry św. Jana. Od tamtej pory aż do początku lat 90. w kościele pw. Podwyższenia Krzyża Świętego Msze św. odprawiano tylko raz do roku – w dniu odpustu, który przypada 14 września. Przez wiele lat odbywały się tu lekcje religii, które do dziś są mile wspominane przez parafian. Dopiero dzięki staraniom proboszcza ks. Mieczysława Panońko i za aprobatą bp. Tadeusza Rybaka wznowiono regularną coniedzielną Mszę św. i nabożeństwa. Przeprowadzono też pierwsze po latach remonty, przystosowując kościół do stałej celebracji. Dziś kościół jest w pełni wyposażony, ma nowy dach, a w najbliższym czasie planowana jest renowacja hełmu wieży, a i to nie jest koniec zamierzeń.

14 września każdego roku olszyńscy parafianie uroczyście dziękują za świadectwo wiary i życia, które dokonywało się w tych wiekowych murach na przestrzeni minionych 700 lat. Jakżeby miało nie być inaczej. W końcu zwycięski Krzyż – znak Chrystusa to droga do nieba i jedyna nadzieja chrześcijan.