Комплекс Караван-сарая состоит из основного корпуса, мечети и минарета; к основному корпусу с двух противоположных сторон примыкают хозяйственные пристройки, называвшиеся «черными дворами», где были конюшни, амбары, погреба.
Главный корпус имеет внутренний двор, полуоткрытый с одной стороны. В центре двора и одновременно на главной оси симметрии комплекса находится мечеть. На этой же оси, имеющей направление с северо-востока на юго-запад, со стороны въезда во двор поставлен минарет. Мечеть с минаретом ориентированы на Мекку. Соответственно ориентирован и весь комплекс. Выходящий на северо-восток фасад – самый протяженный. Его длина составляет 86 м 22 см. Ширина этого корпуса около 10 м. Оба примыкающие к нему крыла имеют длину 49 м 46 см и ширину 16 м. Объёмы с южной стороны имеют длину 25 м 62 см и ширину 10 м 90 см. Высота главного корпуса до крыши 8 м 50 см.
О достоинствах и особенностях Караван-сарая хорошо и подробно рассказал в своей работе «Караван-сарай в г. Оренбурге» архитектор Барый Гибатович Калимуллин. Он выделяет как самое главное и наиболее ценное ансамблевое качество «соразмерность отдельных частей комплекса»стройность общего силуэта, согласованность всей композиции». По формам здания сильно отличаются, но они соподчинены и дополняют друг друга. Хорошо сказано о развитии композиции в высоту: «С низких, горизонтально протяженных стен хозяйственных пристроев взгляд переходит к стенам основного здания и угловым башенкам над крышей, следует выше к куполу мечети, затем поднимается к минарету, его конусному завершению, шпилю и, наконец, уходит в необъятный простор неба».
Анализируя архитектурный образ Караван-сарая Калимуллин приходит к заключению, что в нём отражена схема летнего башкирского аула. Ассоциацию с аулом усиливают возвышающиеся над крышей угловые башенки, которые напоминают лёгкие летние юрты. Интерьеры основного корпуса предельно просты, никакой пышности нет и у фасадов. А. П. Брюллов полностью учел замечание В. А. Перовского о том, что мастера в Оренбурге редки и они очень дороги. Прямоугольные окна фасадов, как внешних так и дворовых, заглублены в нишах, имеющих трех лепестковые или килевидные арки. Это решение придает зданию восточный колорит. Внешние углы здания выделены сужающимися кверху ризалитами, каждый из которых завершен башенкой. Переход к ней решен расширяющимся кверху сталактитовым фризом. Ризалиты с башенками расположены попарно и выделяют также вход во внутренний двор.
Центральный элемент комплекса – мечеть. Её восьмиугольная форма необычна. В этой связи вполне обоснованным представляется объяснение, данное Б. Г. Калимуллиным в упомянутой работе, что А. П. Брюллов стремился придать мечети форму тирмэ (войлочная кибитка, юрта; ставилась как жилище старейшины в центре летнего башкирского аула). Об этом говорит не только общее сходство силуэтов и лаконичность архитектуры, но и отсутствие такого обязательного элемента здания как михраб (молитвенная ниша, указывающая направление на Мекку, решается обычно апсидой – полуцилиндрический или многогранный выступ здания, которому внутри соответствует большой запад или ниша).
Конструктивно в мечети три элемента: восемь одинаковых стен, купол и контрфорсы по всем восьми углам, гасящие боковой распор купола. Большие стрельчатые окна придают зданию определенную лёгкость, а их арки служат для передачи давления купола на стены в углах здания, усиленных контрфорсами.
Если интерьеры главного корпуса предельно просты, то интерьер мечети был достаточно репрезентативен (сейчас он недоступен для обозрения, поскольку основная часть скрыта куполом планетария). Мечеть внутри представляла собой один обширный зал, лишенный мебели, только напротив входа, несколько правее оси, на которой стоит минарет, находилась деревянная кафедра с шатровым верхом, увенчанным шпилем с позолоченной луной. В обработке интерьера применены пилястры, играющие не только декоративную, но и конструктивную роль: они усиливают стены по углам здания. Карниз, отделяющий купол от стен, составлен из классических профилей. Капители пилястр являются одновременно пятами арок. Лицевая сторона их имеет форму неправильного пятигранника и, по определению Б. Г. Калимуллина, напоминает нагрудник башкирки.
Большое впечатление производил интерьер купола, разделённый горизонтально на три части, верхняя из которых решена в виде синего неба. В центре его расположено сияние, лучи которого образуют восьмиугольную звезду. Все это позолочено. От середины сияния опускалась хрустальная люстра. В описании, помещенном в брошюре «Караван-сарай», где, к сожалению, не указан более ранний источник, откуда оно взято, говорится: «люстра… убранная бесчисленным множеством небольших шестигранных хрустальных призм, такими же хрустальными частицами украшены богатые канделябры, утверждённые по углам стены. Солнечные лучи, проходя сквозь разноцветные стёкла разных рам, принимают радужные тени и потом, переламываясь и отражаясь в несчетном числе этих кристаллов, производят необыкновенный эффект на посетителя» .
В средней части купола, разделенной на восемь полей радиальными тягами, размещены лепные узоры и большие восьмиконечные звезды в центре каждого поля. На стенах, оштукатуренных под мрамор, были помещены изречения из Корана.
Необходимо заметить, что в прошлом, когда строился и завершался Караван-сарай и затем вплоть до 80-х гг. XIX в., он производил несколько иное эмоциональное воздействие, потому что и окружение, и масштабность были другими. Это ясно выступает, например, в тех нескольких словах, которыми проезжавший осенью 1842 г. через Оренбург доктор философии и естествоиспытаель Теодор Фридрих Юл. Базинер характеризовал эту постройку: « ..взгляд невольно переводишь на другую сторону слева от дороги, где отдельно стоящее грандиозное здание приковывает его своей необычной красивой архитектурой». Теперь слово «грандиозный» вряд ли было бы применимо – изменилась среда. Комплекс стал и ниже по отношению к окружающей местности – к проезжей части улиц и тротуарам.
Интересен выбор места. Хотя город был ещё крепостью, вопрос об упразднении которой ещё не стоял, Караван-сарай поставлен явно в расчете на то, что рано или поздно крепости не будет, город расширится и минарет мечети будет выполнять определенную градообразующую роль: он поставлен точно в створе Введенской улицы (сейчас 9-го Января). Видимо, решая вопрос о месте комплекса, строители считали, что потомки выведут улицу прямо на Караван-сарай. Так, к сожалению, не случилось.