Храм построен по проекту академика архитектуры А. В. Щусева, составленному в 1908 г. Руководил работами архитектор А. М. Рухлядев. Композиция и архитектурный образ являются творческой переработкой зодчим форм древней псковско-новгородской архитектуры. Храм кирпичный, облицованный снаружи хорошо обработанным известняком, внутри оштукатурен. Сооружение трехмастное, однокупольное. В основе плана прямоугольник, включающий неф, от которого стеной с портальной аркой отделена алтарная часть с маленькой полукруглой апсидой; квадратный в плане притвор уже нефа. С севера примыкает небольшая ризница, с юга - колокольня. Перекрытия сводчатые. Купол - полусферический свод на высоком круглом барабане - завершен большой непропорциональной сооружению луковичной главой, придающей сооружению архаичность. Стены центральной части щипцовые, западный притвор - в форме кокошника, боковые - срезаны под крутой скат, продолжающий уклон нефа. Кровля медная, купол покрыт железом. Под всей церковью и колокольней подвал, перекрытый системой крестовых и полуциркульных сводов, выполненных в кирпиче и бетоне. Вход в подвал с восточной стороны по крутой кирпичной лестнице. Главный фасад богато украшен резьбой по камню. Пилястры, фланкирующие главный вход, украшены розетками с погрудными изображениями. Орнаментом растительного характера покрыт тимпан фронтона западного фасада, между окнами барабана купола и на стенах резные вставки, на южной стене нефа большой горельеф. Резьбу по камню выполнили скульпторы С. Т. Коненков, А. Т. Матвеев, С. А. Ивсеев, мраморщики Ваганьковского кладбища В. Елизаров, С. Круглов, Е. Соколов. Над входом мозаичные изображения. Интерьер, расписанный художником А. И. Савиновым, при советской власти был забелен. Колокольня кирпичная, облицована, как и церковь, известняком, двухъярусная, соединена с церковью переходом с крыльцом. Первый ярус - квадратный в плане, второй - восьмигранный, образован пилонами, соединенными между собой полуциркульными арками, завершен шлемовидной позолоченной главой.
На северном фасаде памятная надпись:
«В лето от создания мира 7419 от Рождества же Господа нашего Иисуса Христа 1911 месяца июня в 29 день в царствование Императора Николая II Александровича в имении Натальевка в присутствии владельцев имения действительного статского советника Павла Ивановича Харитоненко с супругой Верой Андреевной и сына Ивана Павловича, дочерей их Елены Павловны Олтв с супругом Михаилом Сергеевичем и Натальи Павловны светлейшей княгини Горчаковой с супругом Михаилом Константиновичем, внучек Ирины и Веры графинь Стенбок заложен храм во имя Всемилостивейшего Спас в знак милости Божьей явленной роду Харитоненко. Строитель храма академик Алексей Щусев, помощник архитектор Рухлядев. Освящен храм сей лета 1913 месяца июня в 7 день».
Одно из самых лучших сооружений подобного типа начала XX века на территории Украины.