До революции лучшими в стране гостиницами славился Петербург. «Астория» и «Европейская», построенные по проектам архитектора Лидваля, считались шедеврами отельного дела и не уступали по комфорту лучшим гостиницам мира. Москва могла похвастаться «Метрополем» и «Националем», в проектировании, строительстве и отделке которых принимали участие лучшие архитекторы России.
Первым советским отелем высшего класса должна была стать «Москва». Решением правительства определено место строительства гостиницы — улица Охотный ряд, на месте бывших купеческих рядов, всего в нескольких сотнях метров от Кремля. Среди самых титулованных архитекторов страны объявили конкурс на лучший проект отеля. В итоге наиболее подходящим был признан проект архитекторов Л. И. Савельева и О. А. Стапрана. Позже к работе над окончательным проектом гостиницы «Москва» присоединился корифей советской архитектуры, автор проекта Мавзолея Ленина, Алексей Щусев.
«1) Избегнуть роскоши дурного тона, но сделать одновременно гостиницу красивой и комфортабельной. 2) Обеспечить действительно современное и высококачественное оборудование гостиницы сигнализацией, отоплением, вентиляцией, санитарно-техническим оборудованием и т. д. 3) Спроектировать и построить все номера, а особенно номера „люкс“, по последнему слову техники, причём вся работа должна быть произведена своими силами и из советских материалов». Так в своей статье Алексей Щусев писал о задачах, которые ставились перед проектировщиками и строителями гостиницы «Москва». Задачи, надо сказать, не из простых. Опыта проектирования и строительства подобных объектов у советских специалистов было не много, не хватало также необходимых строительных и отделочных материалов советского производства. Некоторые эксперты считают, что при возведении «Москвы» без помощи иностранцев и использования импортных стройматериалов не обошлось. Даже если и так, это абсолютно не умаляет заслуг советских архитекторов и строителей, благодаря которым «Москва» появилась на свет.
В 1932 году проект гостиницы «Москва» был утверждён, после чего и началось строительство. С самых первых дней история строительства обрастала различными легендами, слухами и загадочными случаями. Один из самых известных мифов — якобы «Москву» построили с разными фасадами… по недосмотру. Фасад на площади Революции значительно отличался от фасада, который выходил на Колонный зал Дома союзов. И всё из-за того, что архитекторы Савельев и Стапран представили на подпись Сталину эскизный проект с разными фасадами. Сталин этот вариант утвердил, а архитекторы, обнаружив ошибку, побоялись исправить уже подписанный вождём проект. Правда, не все специалисты верят в эту версию появления несимметричных фасадов гостиницы «Москва».
«Скорее всего, эта красивая легенда была выдумана самим Щусевым, — рассказал в интервью газете „Известия“ член президиума Экспертно-консультативного совета при главном архитекторе Москвы Алексей Клименко. — Строительство гостиницы Моссовета началось в 1932 году… Как раз в это время советская архитектура переключилась на имперскую классику, поэтому исправлять фасад уже наполовину возведённого здания поручили академику Щусеву. По первоначальному проекту гостиница должна была занять весь квартал, но до войны построили лишь половину. Новый корпус дорабатывался другими архитекторами и появился в середине 70-х годов. Вот так „Москва“ стала жертвой времени и переменчивой моды».
Нет единого мнения и по поводу различных секретных объектов, якобы находившихся в «Москве». Один из угловых номеров, с виду ничем не отличавшихся от других, имел стены толщиной в полтора метра, которые не мог взять ни один отбойный молоток. Естественно, возникло предположение, что этот номер не что иное, как секретное убежище Лаврентия Берии. Немало слухов ходило и по поводу того, что в подвалах «Москвы» якобы находится бункер «вождя народов» Иосифа Сталина. Так или иначе, каких-либо документальных подтверждений этим фактам не обнаружено.