В ноябре 1934 года на заседании президиума горсовета председатель горисполкома Е. С. Алфеев предложил построить в городе образцовый ресторан. Здание должно было включать не только ресторан, но и гастроном. Курировал строительство директор КМК К. И. Бутенко. За образец гастронома был взят знаменитый московский «Елисеевский» гастроном. Изначально строительство планировали закончить в 1936 году, но работа затянулась. Открытие гастронома состоялось 21 апреля 1938 года. Он состоял из четырех отделов. Автор этого проекта неизвестен.
Ресторан стал зримым воплощением перехода от конструктивизма к неоклассицизму в архитектуре. Архитектурный стиль ресторана - арт-деко. Для декоративной отделки был приглашен немецкий архитектор и дизайнер Вилли Ламмерт. Кроме лепнины зал ресторана и гастронома украшали фризы с фруктовыми натюрмортами.
Первый крупный ремонт «Москвы» прошел в 1958 году.
В 1964 году провели капитальный ремонт. Реконструкцию осуществил архитектор М. Е. Черненко.
В 1999 году ресторан открылся после очередного ремонта. Были обновлены перила парадной лестницы, из Объединенных Арабских Эмиратов привезена хрустальная люстра, первый этаж отделан мрамором и зеркалами. На пятом этаже оборудовали диско-клуб и казино. Курировал ремонт генеральный директор объединения «Рынки Кузбасса» Юрий Моисеевич Асаилов.
После нескольких ремонтов свой первоначальный архитектурный облик здание частично утратило.
На месте гастронома в настоящее время находится отделение банка.
Памятник архитектуры и градостроительства местного (муниципального) значения (Постановление Коллегии Администрации Кемеровской области от 20.12.2007 № 358).