Проект был утверждён 19 января 1837 года, архитектором назначается А.П. Брюллов. При активном участии башкир были осуществлены сбор средств и строительство комплекса. Изготовление строительных материалов, их транспортировку и все основные работы также выполнялись башкирами. Торжественное открытие Караван-сарая были приурочены ко дню рождения царя Николая I и состоялись 30 августа 1846 года. По случаю открытия был устроен грандиозный праздник.

После ликвидации управления Башкирским войском в 1865 году Караван-Сарай был незаконно отобран у башкирского народа. По распоряжению губернатора В. Обручева в здании были размещены квартира и канцелярия начальника Оренбургской губернии, губернские присутственные места, комиссия по размежеванию башкирских земель. Для служителей мечети были оставлены две небольшие квартиры. Это вызвало возмущение башкир, под жалобой о возвращении незаконно отнятого Караван-Сарая подписалось около 10 тысяч человек.

II Всебашкирский съезд, проходивший в Оренбурге с 20 по 27 июля 1917 год, специально обсудил вопрос о возврате башкирам отнятого у них царским правительством: Караван-Сарая и вынес постановление: «Караван-Сарай как здание, построенное башкирами… съезд объявляет национальной собственностью башкирского народа». На курултае башкир в августе 1917 года был поднят вопрос о возврате Караван-сарая башкирам: «Потребовать, чтобы „последний был освобождён и представлен Центральному шуро“, поручить президиуму заявить об этом Керенскому и Оренбургскому комиссару».

Председатель бывшего Башкирского областного бюро и член Комиссариата по делам мусульман при Наркомнаце Ш. Манатов в январе 1918 г. беседовал по этому вопросу с В.И. Лениным. В.И. Ленин с большим интересом и участием рассмотрел проект декрета о возвращении Караван-сарая башкирам; он спросил: «Караван-Сарай до сих пор ещё не возвращён башкирам?». И тут же сказал: «Надо его скорее отдать». Прочитав подготовленный проект, он вставил между словами «Башкирский дом» слово «народный».