Предыдущая приходская церковь, также деревянная, когда и кем была построена, неизвестно. Однако есть информация, что святыня построена в 1706 году. По состоянию на конец XIX века, церковь находилась в очень плохом состоянии. Община решила ее разобрать. Церковь купили прихожане села Мышковцы (сегодня в Збаражском районе), которые после полного ее восстановления пользуются ею до сих пор.
Жители Залесцев на месте древней в 1898 году начали строить (почему-то этот год ошибочно указывают как окончание строительства) новую большую деревянную церковь. В 1901 году ее завершили и 22 октября этого же года ее освятили. Неизвестно, была ли церковь действующей в советский период. Принадлежит к памятникам архитектуры. В пользовании православной общины Московского Патриархата.
Церковь располагается сразу с востока от нового каменного храма (возведен в 2009 году), в центре села, с запада от кладбища. Удлиненная в плане трехдольная одноверхая. В центре - большая нава с двумя ярусами окон и боковыми входами. На углах ее крыши - четыре башни с макушками. Несколько более широкая деревянная двухъярусная колокольня примыкает с запада к бабинцу. Небольшие ризницы пристроены из обоих сторон к алтарю. Наружные стены церкви заново крашены.
Источник: "Деревянные церкви Западной Украины" http://decerkva.org.ua/ter/zalistsi.html