Клейну пришлось решать такие сложные художественные задачи, как оформление двадцати двух залов в разных исторических стилях, разрабатывать ранее не предусмотренные в программе конкурса проекты двориков, крытых стеклом, – греческого и итальянского, парадного зала, неоднократно переделывать главную лестницу и т д. Одни из этих задач вызывались необходимостью размещать внутри здания архитектурные фрагменты огромных размеров. Другие, как, например, изменение ионического стиля парадной лестницы на греко-римский, объяснялись тем, что в процессе постройки главный меценат музея миллионер Ю.С. Нечаев-Мальцев пожертвовал огромную сумму на облицовку здания снаружи и внутри мрамором лучших сортов.
В ходе работы Клейн неоднократно ездил за границу для изучения европейских художественных музеев и памятников, консультировал план московского музея с крупнейшими авторитетами в области археологии и музееведения, заказывал в Афинах модели деталей Эрехтейона, по которым создавал колоннаду главного фасада – «самый обширный классический портик в России».
Клейн поддерживал тесные контакты с крупнейшими строительными фирмами, как отечественными, так и заграничными, поставлявшими мрамор и зеркальные стекла, бригады камнерезов и штукатуров. Кирпичные стены музея возводили тверские и владимирские крестьяне-артельщики, обрабатывали фундамент из финляндского гранита петербургские каменщики, штукатурили здание итальянские рабочие, обрабатывали мраморные детали, профилировали колонны итальянцы-камнерезы. Белый мрамор для облицовки фасада добывался на Урале, цветные мраморы для отделки интерьеров везли из Венгрии и Греции, Бельгии и Норвегии.
Здание музея, по словам Цветаева, «строилось на века».
«В архитектурной композиции, – писал Клейн в своем «Руководстве к архитектуре», – порядок проявляется в расположении здания. При этом исходят от внутреннего ядра, от сердца распланировки, доводят до развития внутренний организм и скелет здания, одевают последний, вырисовывают в перегибах, в главных частях и обряжают внешний вид посредством расчленения и украшений. Такой прием ведет к цельности организма, к единству в архитектуре… мы имеем перед собой не конгломерат отдельных, случайно нагроможденных кусков, а неделимое целое».
«Последнее сооружение, – сообщала Академия художеств, представляя Клейна к званию академика и награждая золотой медалью, – своими необычно обширными размерами, сложностью и разнообразием архитектурных задач, строгостью присвоенного Московским университетом классического (греко-римского) стиля и монументальностью строительных материалов займет одно из первых мест в Москве, составя се украшение на долгое время».
При постройке музея Клейн подчас оказывался как бы «между двух огней». С одной стороны, профессор Цветаев требовал соблюдения исторической и научной точности при разработке деталей и оформления залов. С другой стороны, меценат Нечаев-Мальцев мог принять или не принять тот или иной вариант, исходя из своих соображений и расчетов. Например, в противовес Цветаеву он одобрил решение Клейном белого зала в форме двухъярусной базилики или парадную прямую лестницу, с которой профессор долго не хотел согласиться, настаивая «на лестнице с поворотами».
Затянувшееся на многие годы строительство здания вызывалось не только грандиозностью решаемых научных и художественных задач, но и главным образом финансовой стороной дела. Музей создавался в основном на частные средства так называемых благотворителей. В общей сумме его стоимости, достигшей около 2, 5 миллиона рублей, государственная субсидия составляла только 200 тысяч, а вклад мецената Нечаева-Мальцева превышал 2 миллиона. Цветаев вкладывал в музей все свои скромные средства, вплоть до «детского» капитала. Клейн годами не получал жалованья, жил доходами от других своих построек и также отдавал музею все, что мог, переживая судьбу этого сооружения как свою личную.
Музей изящных искусств был завершен в 1912 году. Оканчивалось строительство при крайне стесненных средствах. Долги заграничным и отечественным поставщикам-кредиторам достигли крупных размеров, и их пришлось погашать еще в течение нескольких лет после открытия музея.
В годы завершения строительства Музея изящных искусств Клейн разрабатывал проект здания кинематографа «Колизей» на семьсот человек на Чистых прудах. Он вел также реставрацию усадьбы «Архангельское», возводил там, при участии архитектора Г. Бархина, храм-усыпальницу князей Юсуповых в палладианском стиле.