Создание музея стало для Клейна делом жизни, так же как и для его организатора профессора Цветаева. Благодаря энергии последнего оно оказалось в центре внимания ученых, художественных, общественных кругов не только Москвы, но и Петербурга, Казани, Киева, Харькова, Одессы, Варшавы, Берлина, Дрездена, Рима, Афин и т. д. Одним словом, создание его приобрело всероссийский и европейский масштаб.
Клейну пришлось решать такие сложные художественные задачи, как оформление двадцати двух залов в разных исторических (со всей научной точностью) стилях, разрабатывать ранее не предусмотренные в программе конкурса проекты двориков, крытых стеклом, — греческого и итальянского, парадного (белого) зала, который он решил как двухъярусную греко-римскую базилику, неоднократно переделывать главную лестницу и т. д. Одни из этих задач вызывались необходимостью размещать внутри здания архитектурные фрагменты огромных размеров (угол Парфенона в натуральную величину и т. п.), которые приобретал Цветаев (коллекция формировалась параллельно со строительством здания). Другие, как, например, изменение ионического стиля парадной лестницы на греко-римский, объяснялись тем, что в процессе постройки главный меценат музея миллионер Ю. С. Нечаев-Мальцев пожертвовал огромную сумму на облицовку здания снаружи и внутри мрамором лучших сортов.
В ходе работы Клейн неоднократно ездил за границу для изучения европейских художественных музеев и памятников, консультировал план московского музея с крупнейшими авторитетами в области археологии и музееведения — В. Дёрпфельдом, А. Каввадиасом, В. Боде, Г. Треем и другими, заказывал в Афинах модели деталей Эрехтейона, по которым создавал колоннаду главного фасада ("самый обширный классический портик в России").
На протяжении пятнадцати лет строительства архитектор имел постоянные контакты с членами комитета по устройству Музея изящных искусств — архитектором Ф. О. Шехтелем, художниками В. Д. Поленовым, В. М. Васнецовым, П. В. Жуковским, учеными Н. П. Кондаковым и В. К. Мальмбергом, В. С. Голенищевым и Б. А. Тураевым, В. В. Стасовым и Н. И. Романовым и другими. Совместная работа связывала Клейна с военным инженером И. И. Рер-бергом, архитекторами Г. А. Шуваловым и П. А. Заруцким, художником И. И. Нивинским, который расписывал интерьеры, и т. д. Клейн поддерживал самые тесные контакты с крупнейшими строительными фирмами, как отечественными ("Мюр и Мерилиз", "Г. Лист", «Готье», "Строительная контора инженера А. В. Бари", "Чаплин и Залесский", «Брусов», и т. п.), так и заграничными, поставлявшими мрамор и зеркальные стекла, бригады камнерезов и штукатуров. Кирпичные стены музея возводили тверские и владимирские крестьяне-артельщики, обрабатывали фундамент из финляндского гранита петербургские каменщики, штукатурили здание итальянские рабочие, обрабатывали мраморные детали, профилировали колонны итальянцы-камнерезы. Белый мрамор для облицовки фасада добывался на Урале, цветные мраморы для отделки интерьеров везли из Венгрии и Греции, Бельгии и Норвегии. Здание музея, по словам Цветаева, "строилось на века".
Такого размаха не знало ни одно строительное предприятие, с которым был связан Клейн. "Я вполне понимаю Ваше увлечение этим великим делом Вашей жизни, — писал архитектору Цветаев. — Это чудное здание и грядущее художественное учреждение способны овладеть всеми силами души, составляя для его творца и отраду, и гордость, и предмет самой чистой и сильной любви. Я вполне понимаю, что Вы сюда уходите, сюда возвращаетесь от других Ваших работ, имеющих характер прозаический сравнительно с этим кругом поэтических Ваших архитектурных мечтаний, полетов и грез".
В основном своем объемно-пространственном решении здание музея строилось как бы изнутри, снаружи этот прием выявлялся системой «врастающих» друг в друга архитектурных форм. Конструктивное понимание внутреннего пространства, его динамики и импульсивного движения позволяло архитектору сообщить облику музея подвижность, трансформировать художественный образ его в зависимости от требований момента. "В архитектурной композиции, — писал Клейн в своем "Руководстве к архитектуре", — порядок проявляется в расположении здания. При этом исходят от внутреннего ядра, от сердца распланировки, доводят до развития внутренний организм и скелет здания, одевают последний, вырисовывают в перегибах, в главных частях и обряжают внешний вид посредством расчленения и украшений. Такой прием ведет к цельности организма, к единству в архитектуре… мы имеем перед собой не конгломерат отдельных, случайно нагроможденных кусков, а неделимое целое".