К сожалению, собранных денег было недостаточно, поэтому строительство откладывалось.
Митрополит Московский Владимир (Богоявленский) освятил место закладки собора только в 1904 г. Строительство началось 22 сентября 1913 г. Такое промедление оказалось роковым, так как начало войны в 1914 г. замедлило темпы возведения собора. К 1915 г. основной объем храма без куполов и детальной отделки был закончен. Архитектор А.Н. Померанцев считал возведение собора, посвященного его святому покровителю, делом всей своей жизни, стремился ускорить работы, даже передал свои сбережения на строительство.
К октябрю 1917 г. огромный храм выглядел почти законченным, за исключением нескольких глав и внутренней отделки. Через год после начала строительства в подклете был устроен придел апостола Архипа, память которого совершается 19 февраля. Год спустя этот придел, по всей вероятности, был заменен новым, более обширным. 16 ноября 1915 г. освятили придел святителя Тихона Воронежского. Он был устроен по инициативе бывшего председателя строительного комитета епископа Верейского Модеста. Придел размещался под южным отделением главного алтаря, вмещал до четырехсот богомольцев. Храм святителя Тихона Воронежского должен был иметь отдельный причт, в нем предполагалось ежедневно служить литургии и панихиды по православным воинам, на поле брани убиенным, а также по почившим жертвователям. Вход в него был устроен отдельный с улицы. Указом Синода от 30 апреля 1916 г. был открыт самостоятельный приход при строящемся Александро-Невском храме на Миусской площади, со штатным причтом из священника и псаломщика и отнесением содержания его на местные средства. Тогда же в храме был оформлен и освящен северный придел во имя святителя Николая. Он был сделан временным с одноярусным деревянным иконостасом и иконами на холстах в рамах, прикрепленными на неоштукатуренные стены. В алтаре помещалось изображение Божиего Ока, а под ним – Богоматерь Покровительница, копия с работы В.М. Васнецова в киевском соборе Святого Владимира.
После Октябрьской революции строительство было прервано. Тогда же упразднили Комитет для принятия и хранения приношений на созидание храма, работавший с 1861 г. В книге «Красное колесо» А. И. Солженицын написал, что москвичи предлагали использовать «грандиозный недостроенный собор на Миусской площади, внутри без единой колонны» для заседаний Учредительного собрания, в надежде, что оно соберется в Москве, а не в Петербурге. В 1920-е гг. службы в соборе прекратились, и его стали использовать как склад. В частности, в нем хранилась после сноса здания панорамы на Чистых прудах свернутая в рулоны Бородинская панорама художника Ф.А. Рубо. В 1930-е гг. обсуждались разные проекты достройки здания: для Дома Радио (проект архитекторов А.Н. Душкина и А.Г. Мордвинова, 1934 г.), проведения экспериментов по разработке акустических систем для Дворца Советов, так как бесстолпное внутреннее пространство было в три раза больше, чем объем зала Большого театра. Пока шло обсуждение, как приспособить храм, в нем разместили склад, в который свезли чугунные детали Триумфальной арки после ее сноса в 1934 г. Детали (колесница Победы, воины, рельефы и прочие работы скульптора И.П. Витали) потом перевезли в Музей Всесоюзной академии архитектуры, расположенный в Донском монастыре. В 1950-е гг. стены храма, частично уже разрушавшиеся от времени, были взорваны. На месте собора с использованием частично его стен и кирпича в 1960 г. был поставлен Дом пионеров Фрунзенского района по проекту архитекторов Ю. Шевердяева и К.Д. Пехояна.