Kyrkan är den äldsta i Poltava. I mitten av 1600-talet fanns det troligen en sidoinhägnad träkyrka; Kristi förklaringskyrka, vilken brann ned 1705. Det är känt från gamla kyrkokrönikor att en lokal präst, Ivan Svitaylo, före 1709 betalade för ersättandet av en gammal träkyrka ägnad Kristi förklaringskyrka - från Poltava klostret Heliga korsets upphöjelse - på platsen för den nedbrunna kyrkan . Enligt folktron deltog tsar Peter I i gudstjänst i kyrkan efter slaget vid Poltava. Åren 1810-1811, när kyrkan förfallit, togs beslut om att den delvis skulle rivas. Bara en inhägnad enkelkupolsida kvarlämnades som påminnelse om kyrkans stora betydelse i det Ryska Kejsardömets historia. År 1837 besökte tsar Alexander II Poltava. Från medel beviljade av tsaren och det som erhållits genom insamling, byggdes 1845 en tegelstensexteriör över träkyrkan vilket skapade intryck av en enkelkupolkyrka. Projektet utformades av arkitekten Andrej Ton. År 1847 byggdes ett tegelstenstorn framför den västra ingången. Från 1875 till 1898 användes kyrkan som regementskyrka för 33:e Infanteriregementet grupperat i Poltava. Under åren 1875-1898 byggdes en tegel- och järnmur längs kyrkans tomtgräns. År 1902 tog synoden för den ortodoxa kyrkan beslut om att genomföra en omfattande renovering av kyrkan. Ödet för Vår Frälsares kyrka i Poltava har varit lyckosamt, eftersom den inte sprängdes eller raserades av bandtraktorer - som många andra kyrkor råkade ut för - under Stalins regim. Före revolutionen 1917 fanns det ungefär 20 kyrkor i Poltava. Vår Frälsares kyrka är en av bara tre lokala kyrkor som överlevde det hemska 1930-talet. Klocktornet sprängdes till exempel 1934. Efter 1942 upptog kyrkan sin verksamhet som en församling till patriarken i Moskva.