Olecko zostało założone w roku 1560 przez księcia Albrechta na pamiątkę spotkania się z królem Zygmuntem Augustem, fundatorem pobliskiego miasta Augustowa. W chwili założenia Olecko było całkowicie protestanckie. W wieku XIX osiedliła się tu większa ilość katolików, którzy w roku 1853 otrzymali własnego duszpasterza. Budowę kościoła rozpoczęto W 1859 roku, poświęcono 1 grudnia 1861, a konsekrował go 27 sierpnia 1862 roku ks. bp Antoni Frenzl. Prawa parafialne Olecko uzyskało 31 marca 1871 roku, gdy Bp F. Krementz erygował parafię p.w. Podwyższenia Krzyża Św. i św. Wojciecha.

Zgodnie z dekretem, nowo powstała parafia weszła w skład dekanatu sambijskiego z siedzibą w Królewcu i obejmowała tereny powiatu oleckiego oraz gołdapskiego. Zaraz po wojnie parafia w Olecku obejmowała teren późniejszych parafii w Wieliczkach, Cichym, Świętajnie, Gąskach i Kowalach Oleckich. W wyniku usamodzielnienia się tych placówek teren parafii uszczuplił się o kilkanaście miejscowości. Dalsze zmiany granic parafii nastąpiły w latach 1974-1978. Wówczas to z terenu parafii wydzielono dwie nowe: w Szarejkach i Szczecinkach. Zmiany polityczne w latach 80-tych pozwoliły na utworzenie większej liczby parafii także w samym mieście.

Kiedy w roku 1987 w Olecku utworzono nową parafię p.w. NMP Królowej Polski, parafia p.w. Krzyża Św. stała się rektoratem. Ponownie podniesiona do funkcji parafii 3 lipca 1989 przez ks. bpa Edmunda Piszcza – Biskupa Warmińskiego. Wraz z reorganizacją struktur kościelnych w Polsce w 1992 roku parafia Podwyższenia Krzyża Św. weszła w skład nowo utworzonej diecezji ełckiej i dekanatu Olecko. 13 maja 1994 Biskup Ełcki Wojciech Ziemba ustanowił kościół parafialny Diecezjalnym Sanktuarium Krzyża Świętego. W 1998 r. z parafii Podwyższenia Krzyża Św. wydzielono jeszcze jedną parafię – Wniebowzięcia NMP. W 2002 r. Biskup Ełcki Edward Samsel dokonał reorganizacji dekanatu Oleckiego. W jej wyniku parafia Podwyższenia Krzyża Św. znalazła się w nowo powołanym dekanacie – Olecko, św. Jana Apostoła, wraz z parafiami: Olecko-Lesk, Cimochy, Gąski, Szczecinki, Wieliczki.

Kult Krzyża Świętego

Krzyż misyjny przy kościele wykonany z drzewa dębowego został ustawiony w 1960 roku na zakończenie misji parafialnych. 10 września 1981 w czasie przygotowania do odpustu, po nabożeństwie wierni wychodzący z kościoła zauważyli strugi płynące z przodu i z prawej strony krzyża pod ramieniem poprzecznym. Sączące się krople koloru czerwonego spływały kilka dni. „Krwawienie” trwało do końca listopada 1981 roku. 2 marca 1982 „krwawienie” ponowiło się. Wierni uznali to za znak – wezwanie i przestrogę. Ludność odczytywała w tym znaku krwawiące rany Chrystusa. Wydarzenie stało się głośne nie tylko w regionie, ale też i w całej Polsce. Zaczęły napływać pielgrzymki z całego kraju. Na odpust obchodzony w wigilię święta, 13 września 1981 r. przybyły pielgrzymki z Warszawy, Białegostoku, Lublina. Zamościa i ze Śląska, łącznie ponad 2 tys. osób . Ówczesne władze państwowe nie interweniowały, a władze kościelne nie zajęły oficjalnego stanowiska. W 1987 r. staraniem ks. S. Tabaki (ówczesnego rektora kościoła) krzyż obudowano, tworząc rodzaj kaplicy na planie kwadratu. W północnej, wschodniej i zachodniej elewacji od przyziemia do 3/4 wysokości kaplicy umieszczono przeszklone okna w formie wydłużonego prostokąta zakończonego półkoliście. Całość budowli nakryta została czterema dwuspadowymi daszkami wykonanymi z dachówki ceramicznej zakończonej krzyżem. We wnętrzu kaplicy umieszczono obrazy – wota oraz tablicę z krótką historią wydarzeń. Ramię poprzeczne krzyża zostało umieszczone w specjalnej gablocie. Krzyż po dzień dzisiejszy otoczony jest żywym kultem.

Od roku 2003, w 25 rocznicę Pontyfikatu Jana Pawła II, przy Krzyżu o godz. 1500 odmawiana jest codziennie Koronka do Miłosierdzia Bożego

Szczególnie z okazji odpustu Podwyższenia Krzyża Świętego (14 września) gromadzą się wierni nie tylko z okolicznych miejscowości, ale także z terenu całej diecezji ełckiej.

1987 – rozpoczęto budowę kaplicy Krzyża.

1989 – przybyły pierwsze piesze pielgrzymki.

1993-94 – wybudowano stacje Męki Pańskiej.

13 V 1994 – Dekret Biskupa Ełckiego ustanawiający Sanktuarium Krzyża św.

14 IX 1994 – Dekret erygujący Drogę Krzyżową wokół kościoła.

17 IX 1994 – Biskup Julian Wojtkowski z Olsztyna w obecności Biskupa Ełckiego, kapłanów i wiernych poświęcił Stacje Drogi Męki Pańskiej i odprawił nabożeństwo Drogi Krzyżowej.

W Roku Jubileuszowym 2000 wykonano dębową obudowę krzyża. Miejsce to stanowi szczególny kult Krzyża św. i Męki Pańskiej.