Jednocześnie z budową twierdzy wzniesiono cerkiew. Zlokalizowano ją na wysokim prawym brzegu Narwi, na fundamentach rozebranego kościoła. Kamień węgielny położono w 1895 roku. Uroczystego wyświęcenia dokonano 29 kwietnia 1899 roku. Świątynię wybudowano z cegły w bizantyjskim stylu z odwołaniem się do architektury moskiewsko-jarosławskiej. Nad środkową częścią umieszczono okrągłe wieże z kopułą. Nad wejściem znajdowała się dzwonnica. Autorem projektu był inżynier Rakint. Ikony w cerkwi były kopiami ikon z soboru w Kijowie. Koszt budowy to 80 tys. rubli. Po I wojnie światowej zegrzyńską cerkiew przekształcono w kościół katolicki i przekazano Wojsku Polskiemu. W niezmienionej postaci przetrwała ona do 1932 r. Z inicjatywy księdza kapelana majora Żołtowskiego, który uzyskał potrzebne fundusze, dobudowano z przodu toskańskie kolumny, zburzono dzwonnicę, zastępując ją dwiema małymi wieżami, usunięto kopułę. Budowla utraciła wschodni wygląd. Zniszczony w czasie II wojny światowej kościół katolicki pozostawał ruiną, którą wysadzono w 1987 roku, oczyszczając plac pod budowę budynków mieszkalnych.
Literatura: Slovo proiznesennoe Ieronimom, archiep. Cholmskim i Varśavskim, pri osvjaśćenii v kreposti Zegż chrama vo imja Sv. Petra i Pavla. ChVEV 1899, s.241-2; Osvjaśćenie Ieronimom, archiep. Cholmskim i Varśavskim cerkvi v kreposti Zegż. ChVEV 1899, s.242-3; SZCZEPAŃSKI Jacek: Cerkiew forteczna w Zegrzu. Spotkania z Zabytkami 1997, nr 2, s. 23, il.; S z c z e p a ń s k i Jacek: Obóz Hurki. Dzieje garnizonu w Legionowie do 1918 roku. Legionowo 1997; (m.in. Rozdział IX. Cerkwie i cmentarz:Legionowo, Jabłonna i Wieliszew, s. 74-83); -Powiat Legionowski na dawnej pocztówce. Towarzystwo Przyjaciół Legionowa, Legionowo 2000,, ss. 69, il.; (m.in. cerkiew śś. app. Piotra i Pawła w Zegrzu do 1932 r., s. 44; cerkiew przebudowana na kościół, s. 46; wnętrze kościoła garnizonowego przebudowanego z cerkwi, s.55);