Finalement, l’église n’a été construite qu’en 1903, et consacrée et dédiée à l’Élévation de la Sainte-Croix le 10 décembre de la même année. En 1904, un prêtre local catholique s’est installé en permanence à Korsze : le prêtre Zimmerman. Le statut de paroisse n’a été accordé à l’église de Korsze que le 22 février 1910.

La première église en style néogothique était de taille modeste, occupant l’espace de l’actuel chœur : elle ne convenait pas aux besoins des fidèles à Korsze. L’église se trouvait sur une petite colline où menait un chemin pavé à la place de l’escalier. Le nombre augmenté des baptêmes et des funérailles recensés dans les registres paroissiaux témoigne de la croissance de la population à Korsze. Les noms de familles polonaises y figurent également. C’étaient probablement des ouvriers polonais partis en Prusse en quête de travail. À  la fin des années 1930, l’église était déjà trop petite pour contenir tous les fidèles catholiques romains de Korsze, bien que la plupart d’habitants du village soient évangéliques. Le 1^er juin 1939, le prêtre Zimmerman a cessé d’exercer les fonctions de curé, remplacé par le prêtre Derra. Celui-ci a quitté son poste, et est parti avec les troupes allemandes à la fin de janvier 1945.

Les années 1950 sont une période de nombreux efforts pour embellir l’église qui ne souffrait pas la comparaison avec ce qu’elle était en 1945. Son éventail d’agréments : des murs rafraîchis, un dallage et un maître-autel impeccables, des bannières de procession, de nouveaux bancs, des confessionnaux, des chasubles constituaient. La paroisse de Korsze attirait de plus en plus de fidèles. Même si des bancs supplémentaires étaient mis pendant les messes, l’église n’était point capable d’accueillir tant de personnes.

Le 9 août 1958, la permission d’agrandir l’église a été obtenue. Une année plus tard, le 18 octobre 1959, l’évêque Tomasz Wilczyński a célébré la consécration de la nouvelle église, un événement sans précédent dans l’Archidiocèse de Warmie après la Seconde Guerre mondiale.

En 1962, le sol a été revêtu en terrazzo, et en 1965, un nouveau maître-autel dont le projet était choisi par les fidèles a été construit. Les travaux ont été suspendus en raison de la mort subite du curé Lachowicz. Le 17 décembre 1967, le prêtre Stefan Winiecki a été nommé le curé, et il est entré en charge paroissiale le 31 mars 1968. L’église était sans cesse embellie. Le 24 septembre 1969, l’évêque Jan Obłąk a béni l’autel de Notre-Dame-du-Perpétuel Secours.