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