Die Kirche befindet sich im südlichen Teil der Stadt, an der Kreuzung der 12-go Lutego-Straße, der Kilińszczaków-Straße und der Zdobywców Wału Pomorskiego-Allee, an der Woiwodschaftsstraße 178 über Trzcianka nach Posen.

Das Gebäude, in dem sich die griechisch-orthodoxe Kreuzerhöhungskirche befindet, wurde in den Jahren 1923 – 1924 als eine bescheidene evangelische Spitalkapelle im eklektischen Stil mit überwiegend neuromanischen Elementen erbaut. In der Ostwand wurde eine Gedenktafel zur Erinnerung an die im Ersten Weltkrieg Gefallenen aus den 1920er Jahren eingemauert. Das Flachrelief zeigt Christus dar, der eine junge Frau mit Kind – die Witwe eines Soldaten – tröstet. Ursprünglich waren an der Wand auch Namen von Gefallenen zu lesen. Die Kapelle wurde auf einem rechteckigen Grundriss mit einer halbrunden Apsis gebaut, in der sich der Chorraum befindet. Ein Teil des Schiffes an der Südwand ist abgetrennt und bildet einen Vorraum, aus dem eine Treppe hoch zur Empore führt. Die Kirche ist ein Saalbau; aus dem Vorraum führt ein offenes Tor mit Korbbogen in das Schiff. Im nördlichen Teil des Schiffes ist ein einfacher, korbbogenförmiger Chorbogen zu sehen. Außer dem Chorbogen trennt eine moderne Ikonostase von 1996 den Chorraum vom Schiff. Autorin der Ikonostase ist die Künstlerin und erfahrene Gemälde- und Ikonenkonservatorin Walentyna Biriukowicz von der Kunstakademie Kiev. Die aufwendigen Holzschnitzereien wurden von Zbigniew Marus aus Stary Chwalim bei Barwice angefertigt. Sämtliche Ikonen wurden von der Autorin selbst geschrieben. In der Königstür sind die Allerheilige Jungfrau Maria und die Verkündigung abgebildet. Darunter sind die Gestalten der vier Evangelisten Matthäus, Lukas, Johannes und Markus zu sehen. In der linken Tür, auf der hohen, halbbogenförmig zulaufenden Fläche, ist die Gestalt des Hl. Laurentius dargestellt, an den Seiten der Hl. Nikolaus von Myra und die Gottesmutter mit dem Jesuskindlein auf dem Schoß. In der rechten Tür ist der Hl. Stephan zu sehen, an den Seiten Christus Rex und die Kreuzerhöhung. Im Gebälk über der Königstür sind folgende Szenen dargestellt (von links): Christi Geburt, Taufe Christi, Auferweckung der Toten, Christus Pantokrator (in der Mitte), Mariä Himmelfahrt, die Ausgießung des Heiligen Geistes und die Transfiguration.

Nach dem Zweiten Weltkrieg wurde das Gebäude als Filialkirche des Pfarrbezirks St. Nikolai genutzt. Später wurde es auch der griechisch-orthodoxen Gemeinde zur Verfügung gestellt und es fanden abwechselnd Gottesdienste beider Religionen statt. Der erste griechisch-orthodoxe Gottesdienst in Wałcz wurde von Priester Teodor Markiv gehalten. Dieses wichtige Ereignis fand am 21. Juni 1959, am Tag der Ausgießung des Heiligen Geistes, statt. Am 25. September 1994, am 35. Jubiläum des Pfarrbezirks Wałcz, verkündete der heutige Erzbischof Jan Martyniak, dass die Kirche nun vollständig der griechisch-orthodoxen Gemeinde übergeben wird. 

Gottesdienste finden werktags und So um 10.00, an Feiertagen um 8.30 und 17.00 statt.