Инициатива строительства храма возникла в начале XX века среди жителей дачных посёлков Торговых служащих, Дубняки и Красная Сосна, расположенных вблизи станции Лосиноостровская Ярославской железной дороги. Основным благотворителем выступил потомственный почётный гражданин, купец Александр Иванович Иванов, пожертвовавший 15 тысяч рублей на возведение церкви. Земельный участок площадью 1 736 квадратных саженей (около 5 806 квадратных метров) был предоставлен крестьянином Сергеем Ивановичем Карповым из его личных владений.
Строительство храма началось в 1914 году. Проект здания был разработан архитектором Владимиром Дмитриевичем Глазовым и инженером С.М. Фоминским; храм задуман в неорусском стиле с использованием новгородско-византийских мотивов. Строительными работами руководил архитектор Сергей Михайлович Ильинский.
2 апреля 1916 года главный престол храма был освящён во имя святых мучеников Адриана и Наталии. Южный придел в честь иконы Божией Матери «Нечаянная Радость» был освящён 21 августа 1916 года, а северный придел во имя блаженного Василия Московского — 18 сентября 1916 года.
В советский период храм продолжал действовать, несмотря на изъятие церковных ценностей в 1922 году и снятие колоколов. 27 июля 1924 года Божественную литургию в храме совершил Патриарх Московский и всея России Тихон.
