Предыдущая церковь из дерева в селе Новый Алексинец была построена примерно в середине XVIII века, поскольку копии метрических книг сохранились с 1762 года. Ново-алексинецкая деревянная приходская церковь, которая существует сегодня, возведена на месте более древней в 1846 году за счет графа Гавриила Ржищевского. В начале 1890-х годов её крыша была покрыта жестью, а церковь оценили как "крепкую". К памяткам архитектуры церковь не относится. Расположена в центре села, к югу от каменной Успенской церкви (возведеной в 2012 году). Старая церковь в плане образует крест, одноэтажная. С обеих сторон к алтарю пристроены ризницы. С запада к притвору прилегает более узкий притвор.
В настоящее время главка и верх церкви перекрыты блестящей жестью, другие крыши – металлопрофилем (им же обили стены восьмерика), окна – металлопластиковые. Внешние стены выглядят будто долго не крашеные, хотя на совсем не старой фото этой церкви цвет стен был насыщен синим. Колокольня деревянная одноярусная, находится с юго-запада от храма.
Храм находится в юрисдикции УПЦ (КП), в 2019 г. преобразованной в ПЦУ.