По приказу командующего войсками Московского военного округа генерал-адъютанта А.С. Костанда для храма было отведено место размером 50 на 50 саженей в центре расположения военных лагерей. Церковь Сергия Радонежского должна была заменить прежнюю походную палаточную шатровую церковь военных лагерей, стоявшую на Ходынском поле. Войск в летних лагерях на Ходынке, разбивавшихся с мая по октябрь, собиралось до 30 тысяч человек, и потребность в большом вместительном храме ощущалась остро. Офицеры ездили молиться в храмы Всехсвятского и Петровского парка.

В марте 1888 года один из почетных граждан Москвы, купец Николай Павлович Каверин, пожертвовал большую сумму денег на строительство гарнизонной деревянной церкви при летних войсковых лагерях. Как указывает С.К Романюк, он посвятил свой дар пребыванию императора Александра III и его супруги в Москве в 1883 году и «Высочайшему смотру» войск на Ходынском поле 28 мая 1883 года.

Дело постройки храма не сразу заспорилось. Н.Г. Каверин не смог в одиночку финансировать все строительство, а первоначальный проект архитектора И.П. Херодинова не был утвержден строительным отделением губернского правления. Но после неудачного покушения на жизнь наследника престола Николая Александровича (будущего императора Николая II) в Японии 29 апреля 1891 года, командующий войсками Московского военного округа А.С. Костанд предложил возвести на Ходынском поле храм в память чудесного избавления цесаревича от опасности и призвал военных и московское купечество жертвовать на его строительство. Число ктиторов увеличилось, и дело сдвинулось. В 1891 году была создана специальная комиссия для сбора средств на постройку. В марте 1892 года был утвержден доработанный проект И.П. Херодипова. Торжественная закладка храма состоялась 24 июня 1892 года, хотя к тому времени храм уже начали возводить: построены были стены и приступали к сооружению шатра.

Сметная стоимость строительства церкви составляла 60 тысяч рублей. Финансировали стройку благотворители — почетные граждане Москвы: С.И. Натрускин, А.М. Михайлов, Я.В. Шилов, И.П. Воробьев, ДБ. Борисов, Н.И. Силуанов, Н.П. Бирюков. Кто-то жертвовал деньги, кто-то на свои средства возводил или обустраивал части сооружения — ограду, кровлю, бетонный пол «в шашку», иконостасы.