9февраля 1872 года был издан указ императора Александра II об учреждении в Москве «Музея имени Его Императорского Высочества Государя Наследника Цесаревича». Этот день считается днем основания Государственного Исторического музея.
В апреле 1874 года Московская городская дума выделила для постройки музея землю на Красной площади, на которой находилось здание Земского приказа, построенное в конце XVII века. В том же году старинная постройка была снесена для освобождения места под новое строительство.
Согласно конкурсному заданию здание музея должно было быть выдержано в стилистике русской архитектуры XVI века, чтобы его облик органично соответствовал сложившемуся к тому времени архитектурному ансамблю Красной площади. По итогам конкурса предпочтение было отдано проекту архитектора Владимира Шервуда и инженера Анатолия Семенова.
Так на Красной площади появилось новое здание, построенное в модном тогда неорусском стиле. Интерьеры здания напоминают теремной дворец. Фасады выполнены из красного обожженного кирпича, как и стены находящегося рядом Кремля. Башни постройки тоже напоминают кремлевские. Декор повторяет мотивы храма Василия Блаженного. Таким образом, мастера добились органического вхождения постройки с многочисленными башнями и высокими фигурными кровлями в ансамбль Красной площади.
Здание интересно не только снаружи, но и внутри. Его интерьеры, внутреннее убранство (росписи потолков и стен, мозаичные полы и решетки) дают наглядное представление об этапах развития России. Владимиром Шервудом выполнены проекты интерьеров парадных сеней и залов. Для их оформления он предложил использовать фресковую живопись и скульптуру. В оформлении Суздальского зала принял участие архитектор П.С. Бойцов. Оборудование и отделку читального зала выполнил архитектор И.Е. Бондаренко. Над отделкой залов работали также московский архитектор А.П. Попов и художники И.К. Айвазовский и В.М. Васнецов.
Строительство здания велось в 1875–1881 годах. В 1878 году Шервуд перестал заниматься проектом, и строительство возглавил архитектор Александр Попов. Музей открылся для посетителей 27 мая 1883 года.