Zasluge za gradnju ove crkve pripadaju prvom paljanskom svešteniku Đorđu Grabežu. Glavni izvođač radova bio je Miloš Miladinović iz Donjeg Vakufa. Crkvu je osvetio mitropolit Evgenije (Letica)30. avgusta1909. godine. U Prvom svetskom ratu austrijski vojnici su u crkvu zatvarali konje. U Drugom svetskom ratu crkva nije stradala ali je uništena crkvena arhiva.
Do sada su poznati paljanski sveštenici: Đorđe Grabež 1890-1917; Milan Lalić 1917-1918; Simo Begović od 1918. do početka Drugog svetskog rata; posle Drugog svetskog rata opet Milan Lalić; Vladimir Šoljević 1947-1952; Dragoljub Savić 1952-1987. Iste godine kada je penzionisan prota Savić osnovana je druga paljanska parohija. Na prvu paljansku parohiju postavljen je Slobodan Lubarda a na drugu Miomir Zekić. U leto 1996. godine osnovana je treća paljanska parohija a za trećeg paroha je postavljen Jeremija Starovlah.
1Pod gradskom cjelinom Istočno Sarajevo, kolokvijalno „Donji grad”, smatra se teritorija opštine Istočna Ilidža i opštine Istočno Novo Sarajevo, kao i dijela opštine Trnovo.