Гостиница «Москва», занимающая целый квартал, стала одной из первых гостиниц, построенных в советской Москве. Массивное здание играет доминирующую роль в формировании района, непосредственно прилегающего к Кремлю. «Москва» отличается сложной архитектурной пластикой, призванной согласовать строение с соседствующими Кремлём и зданием Исторического музея.

Охотный ряд, считавшийся в начале XX века одним из самых антисанитарных районов города, стал первым московским районом, подвергшимся коренной реконструкции в 1920-е годы. Ещё в 1922 году здесь планировали возвести Дворец труда. Проведённый представительный конкурс на лучший проект не привёл к воплощённым результатам. В силу финансовых трудностей строительство было отложено. Однако работы по реконструкции застройки начались: в том же году снесли часовню Александра Невского на Манежной площади, в 1924 году начался массовый снос торговых лавок в южной части Охотного Ряда (преимущественно деревянные строения). В 1928 году снесли церковь Параскевы Пятницы, а всю рыночную торговлю перенесли на Цветной бульвар.

В середине 1931 года объявили открытый конкурс на строительство новой гостиницы Моссовета, на который было подано 6 проектов. Два из них выполнили архитекторы Госпроекта (первый — Г. Б. Бархин и Н. Н. Юргенсон, второй — И. П. Лобов), два — архитекторы Мосстроя (авторы первого Б. Н. Блохин, А. М. Зальцман и Я. А. Корнфельд, второго — О. А. Стапран и А. А. Зубин), по одному проекту выполнили П. А. Голосов и Институт сооружений. Так как конкурс не принёс желаемых результатов, Моссовет поручил Моспроекту провести ещё один, уже закрытый конкурс среди своих сотрудников. Первый проект выполнили сотрудники архитектурной мастерской А. В. Щусева О. А. Стапран и Л. И. Савельев, при консультировании Щусева, второй коллектив авторов (А. А. Кеслер и И. З. Вайнштейн) консультировал М. Я. Гинзбург, третий заказ получил работавший в то время в Москве немецкий архитектор Бруно Таут.

По итогам закрытого конкурса лучшим признали проект молодых сотрудников щусевской мастерской Стапрана и Савельева и приняли его к реализации. Проект был решён в духе конструктивизма и входил в очевидное противоречие со сложившимся историческим обликом района. Суровый аскетизм массивного здания не увязывался с ансамблем Кремля, застройкой Охотного Ряда, Тверской и Моховой улиц. К тому же следует иметь в виду, что в начале 1930-х годов в советской архитектуре начался процесс отхода от авангардных направлений, наметился явный поворот в сторону переосмысления классического наследия прошлого, впоследствии приведший к возникновению архитектуры «сталинского ампира».

Строительство гостиницы начали весной 1932 года. Сначала Моссовет поручил вести работы Металлострою, затем заказ передали Мосстрою, а в августе того же года создали Управление по строительству гостиницы Моссовета — самостоятельную организацию, прямо подчинённую президиуму Моссовета. Строительство такого масштабного здания было сложной задачей для страны и поэтому в проект были включены уже имеющиеся здания Гранд-Отеля и гостиницы «Московская», где были сохранены шикарные интерьеры знаменитого дореволюционного ресторана, в котором некогда пел Ф. И. Шаляпин.

В качестве соавтора, призванного исправить «ошибки» проекта, пригласили Алексея Щусева. Каркасная коробка здания к тому времени уже достраивалась, и внести значительные изменения не представлялось возможным. Однако Щусев с большой изобретательностью и тактом внёс изменения в проект, добавив лаконичный декор в духе неоклассицизма, не нарушив при этом конструктивистскую основу проекта здания. В результате появился строгий и монументальный восьмиколонный портик высотой в шесть этажей с открытой террасой, просторные лоджии-аркады по центру главного фасада, многочисленные балконы. Углы здания были акцентированы башенками. Само здание приобрело бо́льшую пластичность благодаря более выраженному членению главного фасада.

Здание изначально планировалось разновеликим: главный фасад имел 14 этажей; корпус, выходящий на Охотный Ряд — 10. Центральный фасад после сноса в 1938 году целого квартала зданий, включавшего здания «Экспортхлеба» и гостиницы «Лоскутная», получил прямой выход на Манежную площадь и был ориентирован на планировавшийся к строительству Дворец Советов, с которым должен был образовать архитектурную связку.

Тогда же Щусев выполнил эскизы второй очереди гостиницы, но до строительства новых корпусов дело не дошло. 10-этажный корпус, выходящий на площадь Революции (фасадом на здание Музея Ленина), и 6-этажный, обращённый к Театральной площади, начали строить только в 1968 году. Архитекторы А. Б. Борецкий, А. А. Дзержкович, И. Е. Рожин, Д. С. Солопов и В. А. Щелкановцева в целом учли композиционные идеи, заложенные предшественниками.

Вторая очередь гостиницы была сдана в эксплуатацию в 1977 году, к 60-летию Октябрьской революции; тем самым корпуса гостиницы «Москва» заняли собой целый квартал. Однако декор новых корпусов получился более сухим по рисунку; 6-этажный корпус вообще был решён в духе обыкновенной бетонной коробки, что внесло, по мнению некоторых специалистов, резкий диссонанс в ансамбль Театральной площади.

Существует легенда о том, что И. В. Сталин лично утверждал окончательный проект гостиницы, представленный Щусевым, и именно это обстоятельство стало причиной заметной асимметрии главного фасада здания и того, что его ризалиты отличаются друг от друга. Согласно этой легенде, архитектор для утверждения подготовил проект главного фасада с двумя вариантами оформления, которые были совмещены в одном чертеже и разделялись осью симметрии: на правой части чертежа был изображён более строгий вариант, на левой части — вариант с бо́льшим количеством декоративных деталей. Сталин поставил свою подпись посредине: уточнить, что именно имел в виду Иосиф Виссарионович, никто из проектировщиков не решился, и Щусев реализовал в одном фасаде оба варианта оформления, в буквальном соответствии с утверждённым чертежом.

Однако известно, что Сталин не занимался утверждением архитектурных проектов, асимметрия же фасада гостиницы обусловлена технологическими причинами: при строительстве второй очереди здания было решено не сносить старый «Гранд-отель», а надстроить его стены до нужного уровня — визуальная толщина, по расчётам, позволяла выдержать надстраиваемые этажи. Однако при надстройке одиннадцатого этажа стены старой гостиницы не выдержали и начали трескаться. Оказалось, что стены «Гранд-отеля» только снаружи выглядели мощными — на самом деле они представляли собой полые коробки, заполненные строительным мусором. Архитекторам пришлось решать задачу по укреплению этих стен и максимальному облегчению строящейся части гостиницы — для этого были заложены оконные проёмы на первых этажах (отсутствие окон на первых четырёх этажах видно на старых фотографиях) и убран весь декор правой башни.

Московские градозащитники делали попытки сохранить историческое здание гостиницы, однако безуспешно. После его сноса в 2004 году открылся красивый вид на Кремль и окружающую его застройку, что вновь заставило специалистов говорить об отмене проекта. Появилось предложение разбить общественный парк на этом месте, мотивированное, в том числе, повышением туристической привлекательности центра города — однако московские власти, будучи соинвесторами строительства, не пошли на это.

Проект нового здания на месте разрушенной гостиницы разработан архитектором ГУП «Моспроект-2 имени М. В. Посохина» В. В. Колосницыным. Заказчиком реконструкции является ОАО «Декмос» (51 % которого принадлежит американской компании Decorum Corp., 49 % — правительству Москвы), который должен был построить новое здание отеля к середине 2008 года, вложив более 800 млн долларов США. Генеральный подрядчик строительства — ЗАО «Штрабаг» (российское представительство австрийского строительного концерна Strabag SE). Торговой частью здания управляет компания Sawatzky.

Общая площадь комплекса составляет 183 000 м². Помимо гостиничных номеров и апартаментов, в комплекс вошли офисы, торговые площади и конгресс-центр. Одна из башен получила дополнительные окна, которые отсутствовали у старой версии из-за своего положения. В 2013 году здание было введено в эксплуатацию.

В ходе реконструкции неустановленные лица украли более 87 млн долларов из выделенных городом на строительство. По мнению профессора МАРХИ Вячеслава Глазычева, целью реконструкции и было воровство, так как никакой особой потребности в сносе гостиницы, построенной в начале 1930-х годов, не было.