Parafię w Zalesiu założył Hieronim Wołłowicz, podskarbi litewski i administrator dóbr królewskich na Litwie. Zapisem testamentalnym z 14 czerwca 1602 r. nadał kościołowi w Zalesiu folwark z zabudowaniami w tej miejscowości oraz wsie Zalesie i Pohorany. Fundację tę zatwierdził król Zygmunt III Waza. W 1618 r. Wołłowicz przeniósł uposażenie parafii na klasztor bernardynek w Grodnie.
Według niepotwierdzonego przekazu, zanim powstał murowany kościół w Zalesiu, już w I-szej poł. XVI w. miała tu istnieć świątynia drewniana, strawiona później przez pożar. Murowany kościół za sprawą fundatora zbudowano w latach 1604-1623, stąd obiekt uznawany jest za najstarszy murowany kościół w Archidiecezji Białostockiej. Prawdopodobnie nosił on wezwanie Wniebowzięcia Najświętszej Maryi Panny.
Na początku XIX w. w źródłach figuruje też tytuł Przemienienia Pańskiego. Tytuł Matki Bożej Pocieszenia pojawił się dopiero po remontach kościoła i jego odnowieniu w 1858 r. przez proboszcza, ks. Józefa Węckowicza. Wtedy m.in. przebudowano obie wieże, a dach pokryto czerwoną dachówką. W latach 1988-1989 wymieniono instalację elektryczną. Gruntownemu remontowi poddano też dach kościoła, m.in. wymieniono blachę ocynkowaną na miedzianą.
W lutym 2005 r. pożar strawił drewnianą plebanię. Nowo mianowany proboszcz, ks. Wojciech Markowski, rozpoczął budowę nowej, murowanej plebanii, którą ukończono w 2007 r. Staraniem ks. Markowskiego, przeprowadzono też prace remontowe w kościele, m.in. wymieniając okna i drzwi frontowe..