Согласно преданию, строительство церкви началось по повелению Петра I. Уже в 1711 году состоялось освящение приделов. Главный престол был освящен в 1717 году. Собственно храм представляет собой двухсветный четверик, перекрытый восьмигранным сводом и увенчанный двумя уменьшающимися по размеру восьмериками и главой. Особую выразительность силуэту храма придают широкие полукруглые фронтоны в центральной части фасадов — так называемые полуглавия. Этот элемент получит позднее самое широкое распространение в русской церковной архитектуре. Расположение и форма оконных проемов четверика в общих чертах воспроизводит схему фасадов второго яруса церкви св. Николая в Троекурове. Возможно, и полуглавия церкви Иоанна Воина — развитие идеи полукруглого фронтона троекуровского храма. Трапезная и колокольня решены в более традиционных формах. Существующий резной иконостас главного храма, относящийся к началу XVIII века, перенесен из разрушенной церкви Трех Святителей у Красных ворот. Заслуживает внимания церковная ограда с коваными решетками середины XVIII века.
Специалисты связывают строительство церкви с творчеством московского архитектора Ивана Зарудного, хотя документальных подтверждений этому не найдено.
