1 мая 1902 года было объявлено о создании управления по постройке Московской окружной железной дороги, а 19 июля началось наконец само строительство. Сохранились фамилии московских купцов и промышленников, строивших дорогу: Шик, Данциг, Масюков, Чаев, Кирст, Богданович, Забелин, Зябкин. Все работы осуществлялись подрядчиками на основании проводимых торгов, определявших цену. Лишь одна работа по копке канавы вдоль соединительной ветки с Николаевской железной дорогой была проведена не на основании торгов. Рытье этой самой канавы на глубине в одну сажень в водоносном слое оказалось настолько сложным, что подрядчики заломили за это неподъемную цену – почти 20 тысяч рублей. Пришлось искать исполнителей на стороне, и работа была выполнена за 8,5 тысячи рублей. Специально в Англии и Германии закупили по два экскаватора для глубоких земляных работ (глубже 3 саженей), один экскаватор изготовили на Путиловском заводе в Петербурге.
Металлические фермы для мостов заказали металлургическим заводам, разбросанным по всей России, – в Варшаве, Николаеве, Дебальцеве, Сормове и других городах. А сами мосты проектировались под руководством признанных и на Западе выдающихся инженеров-мостостроителей Николая Аполлоновича Белелюбского, Лавра Дмитриевича Проскурякова и известнейшего зодчего академика Александра Никаноровича Померанцева, отвечавшего также за архитектуру всей дороги.
Лишь один мост своим названием был связан с топонимикой – Дорогомиловский. Другие же мосты назвали в честь представителей царской семьи – Алексеевский, в честь наследника престола цесаревича Алексея Николаевича (ныне Даниловский); Николаевский, в честь императора (позднее Краснолужский); Сергиевский, в честь убитого великого князя Сергея Александровича, бывшего генерал-губернатора Москвы (ныне Андреевский). Имелось и два малых моста, через Яузу и Лихоборку.
С началом в 1904 году русско-японской войны и последовавшим в 1905 году обострением внутриполитической обстановки в стране строительство дороги осложнилось. Необходимость больших военных расходов привела к тому, что объемы кредитов на прокладку железной дороги существенно сократились, отсрочив плановое завершение работ. С другой стороны, забастовочное движение, саботаж на железной дороге не позволили своевременно подвезти комплектующие материалы для сооружения мостов к Москве, что также не способствовало быстрому окончанию строительства.
Непросто шел процесс отчуждения земли под прокладку дороги, как это часто у нас случается, нашлось немало желающих нажиться на этом путем скупки участков и недвижимости, обреченной на снос. Для этого власть решила ввести в заблуждение собственников земли, сообщив им, что в случае назначения ими слишком большой цены дорога может пройти по другому направлению (хотя это было блефом). Специально делались изыскания в тех местах, где дорога в принципе никогда бы не прошла – чтобы ни у кого не было уверенности в высокой ценности его владения и безальтернативности присходящего. Но и собственники не сидели сложа руки, в оперативном порядке засаживая свою землю деревьями-крупномерами, чтобы под предлогом наличия «сада» сорвать куш побольше. А некоторые срочно стали возводить всякие сараи и амбары. Всего было затронуто отчуждением 366 участков земли и 230 строений. В целях недопущения спекуляции всё постарались сделать быстро: сразу после направления собственнику официального извещения о будущем изъятии земли и составления описи ему предлагали заключить добровольное соглашение по цене земли. С назначенной ценой согласились почти все – 92 % собственников, оставшиеся же потом еще долго разбирались с Оценочной комиссией.