Характер музея определился не сразу. Поначалу предполагалось создать Музей военной славы России. На состоявшемся 11 февраля 1872 г. «Севастопольском обеде» был прочтен рескрипт наследника престола о том, что вещи из севастопольского отдела Политехнической выставки останутся в Москве как часть проектируемого военного музея. Затем предполагалось создать Музей истории великих и значительных событий государства. Уваров разработал научную концепцию музея, «представляющего историческое развитие во всех видах минувшей жизни и связи с историей народов, когда-либо проживавших в пределах России». Прекрасный организатор науки, Уваров понимал значение Забелина в организации первого национального исторического музея. Знал и своенравный характер Забелина, но терпеливо привлекал ученого к сотрудничеству. Сложность создания музея, непредсказуемость развития событий, трата времени на заседания, обсуждения в комитетах и комиссиях не привлекали стремившегося к кабинетной работе историка. Руководя большими археологическими раскопками, Забелин понимал, сколько сил, времени, волнений потребует новое дело. В дневнике прослеживается некоторая предубежденность Забелина по отношению к графу, нежелание быть используемым в чужих интересах. Отказываясь от службы, он объяснял Уварову, что положение, которое имеет сейчас, получил «с бою», тяжелейшим трудом.
Но уже в 1872 г. Забелин вошел в состав комиссии по постройке здания, в 1874 г. — в состав ученой комиссии музея для решения вопросов об облике здания, его залов, принципе отбора экспонатов и т. д. В состав комиссии входили также С.М. Соловьев, В.О. Ключевский, Д.И. Иловайский, В.Е. Румянцев, но подлинными отцами-основателями музея можно считать Уварова и Забелина.
В апреле 1874 г. Московская городская Дума постановила безвозмездно предоставить для постройки музея лучшее место в городе — на Красной площади. Организационная структура музея была оформлена 2 августа 1874 г. В соответствии с ней музей имел право собирать исторические материалы, принимать пожертвования, устраивать публичные чтения, лекции, иметь свои издания, библиотеку, учреждать премии и медали. Ученой комиссией была сформулирована программа, обязывавшая архитекторов ориентироваться при составлении проекта здания на особенности русского зодчества XVI века, «потому что в это время есть черты своеобразные, и их-то и требовалось выделить как русские и создать на их основании единое целое»[35]. В обсуждении проекта, предложенного архитектором В.О. Шервудом, принимали участие не только ученые, но и представители городских властей. Дневники Забелина передают атмосферу непонимания и принципиального разногласия между членами комиссии. В ноябре 1874 г. управление решило провести конкурс на лучший проект. На конкурс были представлены работы Р.А. Гедике, Л.В. Даля, А.Е. Вебеа, А.С. Каминского, А.П. Попова, Н.А. Шохина, И.П. Херадиононова, Ф.О. Шехтеля, В.О. Шервуда. Лучшим был признан переработанный проект В.О. Шервуда и А.А. Семенова под девизом «Отечество».