A templomok az elmúlt évszázadokban a közlekedési utak főtengelyében, a településszerkezet meghatározó elemeként helyezkedtek el. Az egykori Leninvárosban a római katolikus hitélet gyakorlására és templomépítésre csak a rendszerváltás után nyílt lehetőség. A templom helyét a város főutcájának északi végén jelölték ki, alapkövét 1991. október 13-án tették le. A tervezési munkát városunk szülötte, Rátkainé Kiss Róza, s férje, Rátkai Attila építészmérnökök végezték. A tervezésnél alapvető szempont volt, hogy a panelépületek között a templom – a rendeltetésén kívül – egyszerű külsejével is felkeltse a figyelmet. Elrendezésében funkcionális, anyaghasználatában pedig a hagyományos megoldásokat alkalmazták a tervezők. Az épületre jellemzőek a vakolt, és a nyerstéglafelületek, a nyitott fedélszerkezet, a fa nyílászárók, a palafedés, valamint a kis fesztávolságok.

Szederkény az ismert források szerint a református községek közé tartozott már a XVI. században is. 1621-ben vált önálló anyaegyházzá. A XVIII. század végéig a település fatemplommal rendelkezett. 1791-ben a falu lakói a vármegyéhez fordultak és egy kőtemplom építési engedélye iránt folyamodtak. A kedvező választ követően a község lakói gyűjtésbe kezdtek, hogy összeszedjék a templomépítéshez szükséges pénzt. Az alapkőletételre 1792. június 18-án került sor.

A görögkatolikus templom építésének gondolata a rendszerváltást követően, a tiszaújvárosi hívők kezdeményezésére született meg, akik templomépítési tervükkel Dr. Keresztes Szilárd, hajdúdorogi megyéspüspököt, miskolci görögkatolikus apostoli kormányzót keresték meg. A kedvező fogadtatás után Nagy József András építészmérnököt kérték fel tervezőnek, aki 1993 őszén bemutatta a bizánci stílusú templom terveit. Ekkorra már helyet is találtak a templom számára, mégpedig az autóbusz-pályaudvar bejáratával szemben, a Szent István út és a Bartók Béla út sarokpontján, az Ifjúsági park szomszédságában.