В 1859 г. ратман городовой ратуши, троицкий купец 2‑й гильдии Гайса Мухаммет-Юсуфович Яушев и с ним еще 10 человек компаньонов ходатайствовали перед начальством «о дозволении построить напротив существующего Гостиного двора другой, каменный, подобного же фасада». Просьба обосновывалась тем, что «Торговая площадь оказалась беспорядочно застроенной лавками, пришедшими в ветхость и представлявшими пожарную опасность». По мысли ходатаев, новый «корпус должен будет заключать в себе 15 лавок и 4 винных погреба со входами с обеих сторон и с галереею вокруг оного длиною 48, шириною 7 сажен…».

В 1860 г. о постройке каменного Гостиного двора подал прошение и бывший городской голова Василий Иванович Зарубин. Первоначальный проект 1860 г. представлял собой сильно вытянутую по горизонтали прямоугольную постройку, разделённую на отдельные ячейки-лавки с обходной галереей по всему периметру сооружения.

Одновременно на площади (возле современного здания городской администрации) началось строительство большой каменной гауптвахты. Вскоре троицкий купец Пётр Михайлович Татаринов обратился с прошением разрешить ему выстроить на той же площади храм во имя Преображения Господня с двумя приделами. Губернские же власти первоначально склонялись к превращению площади в плац-парадную и в 1860 г. даже приступили к планированию местности между старым Гостиным двором и строящейся гауптвахтой. В 1861 г. разрабатывается вариант проекта Гостиного двора, охватывающего северную часть Торговой площади. Посему купец П. Татаринов отступил от плана строительства церкви на площади и в том же году выразил желание построить храм на кладбище при монастырской общине, выделив на это 6 тыс. руб. На площади же в 1862 г. начался снос частных лавок, мешавших «разбивке местности идеальной плац-формы». Правда, вскоре военным пришлось отступить от своих замыслов и в 1866 г. снести построенную гауптвахту, т. к. годом ранее троицкому купечеству наконец было дозволено устроить каменные лавки. Из проекта плана Троицка 1865 г. видно, что Гостиный двор должен был состоять уже из двух Г-образных в плане корпусов. Тогда же Городской голова Василий Михайлович Пупышев, выступил с новым предложением строительства на площади каменной «приходской» церкви. Выкопировка с плана Троицка, где были показаны расположение проектируемых Гостиного двора и храма во имя Архистратига Божия Михаила, была утверждена императором Александром II 2.06.1867 г. Решение Строительного отдела Оренбургского губернского правления было принято в апреле 1868 г. Месяцем раньше контракты с Городской думой на взятие в аренду мест под постройку каменных лавок заключили: троицкие 1 гильдии купцы Гайса Юсуфович Яушев, Василий Ипатович Зарубин и Ахмеджан Халитович Бакиров; 1 гильдии купеческие сыновья Иван Васильевич и Михаил Васильевич Пупышевы, Мухамметгалий Исхакович Халилов; купцы 2 гильдии Муса Абдуллин, Алексей Климович Берёзкин, Габидулла Илялов, Василий Давыдович Мельников, Гурьян Степанович Смирнов, Иван Павлович Зарубин, Фёдор Алексеевич Муталов, Иван Фёдорович Разсохин, Гаврила Алексеевич Крюков, Александр Леонтьевич Осипов, Василий Алексеевич Афанасьев; 2‑й гильдии купеческие сыновья Сейфулла Габбасов, Иван Васильевич Лебедев, Иван Александрович Осипов и Иван Николаевич Зарубин и Фазыл Учаров.

5 июня 1868 г. в Троицк для участия в церемонии закрытия Оренбургской и Сибирской таможенных линий и объявлении русскому и азиатскому купечеству Высочайшего повеления о свободной торговле на местном Меновом дворе прибыл Великий князь Владимир Александрович. Через три месяца троицкая Городская управа приняла в своё ведение Меновой двор и здания бывшей пограничной таможни. 30.10.1868 г. управа въехала в апартаменты бывшего таможенного присутствия (нынешний узел связи). Следы проведённой тогда перепланировки помещений по проекту «архитекторского помощника» Черфолио заметны до сих пор. После городовой реформы 1870 г. и появления Городской думы для проведения её заседаний управе пришлось арендовать помещения в доходном доме Яушевых (2‑й этаж ТФ ЧелГУ), который фасадом выходил на площадь.

Возвращаясь к визиту Великого князя, надо сказать, что 6 июня в 11 часов утра он принял участие в торжественной закладке здания новой церкви на площади. После речи, сказанной протоиереем Гавриилом Аманацким, «было приступлено к закладке храма, причём Его Императорское Высочество своеручно клал монеты золотые и серебряные… в металлический ящик, который был опущен в углубление, заложенное своеручно Его Высочеством плитою каменною». Естественно, что Августейшему примеру последовали все участники этого события, заполнив ящик почти доверху. Церковь была заложена с двумя пределами — во имя Св. равноапостольного кн. Владимира и Св. Василия Великого. На сооружение В. М. Пупышев затратил 60556 руб. 30 коп., а в 1883‑1884 гг. на выделенные им же 3500 руб. была воздвигнута ограда вокруг храма. Строительство шло под наблюдением представителя Инженерного управления Оренбургского военного округа поручика Ивана Дмитриевича Лебедева. По свидетельству Н. Шмотина, проект храма был составлен одним из лучших столичных архитекторов. Церковь была пятиглавой, с колокольней, которая размещалась в передних куполах и представляла собой образец «шатрового» варианта русско-византийского стиля. Собственно храм был украшен скупо. Главные украшения были сосредоточены на барабанах и куполах: узкие арочные сдвоенные окна, килевидные кокошники, венец круглых розеток на главном куполе, этот же мотив — на малых куполах, сами купола — шатровой формы с башнеобразными завершениями.

Храм этот играл важную роль и как высотная доминанта в силуэте города, и как формообразующий элемент в ансамбле площади. Приходская жизнь началась в нём в сентябре 1876 г., но до 1894 г. он был приписным к Троицкому собору. Михайловская церковь и Первая соборная мечеть, возвышавшиеся в центре города, символизировали православную и мусульманскую общины города, точнее их состоятельные купеческие прослойки. Знаком их единства, общего дела раскинулся между ними Гостиный двор. Священник Николай Шмотин писал с восхищением в 1870 г., что в Троицке «строится отличный Гостиный двор, который состоит внутри города и составляет особенную красу его». Строился он с 1868 г. до начала 1870‑х на южной половине Торговой площади, ставшей отныне «Михайловской» и занял целый квартал главной улицы города — Оренбургской. Крылья его аркад развернулись вдоль соседних Васильевского и Николаевского переулков. Он представлял собой одноэтажное кирпичное оштукатуренное здание (120х73 м) со стропильной вальмовой крышей. Постройка, напоминающая при взгляде сверху букву П, так как было решено соединить обе Г-образные части, имеет симметричную композицию планов и фасадов; разделена на ряд изолированных друг от друга отсеков (лавок). По периметру здания проходит арочная галерея. Основания арки имеют эллиптическую форму, угловые — полуциркульную, их пролет меньше, чем у основных. Здание относится к традиционному типу гостиных дворов, строившихся в эпоху классицизма повсеместно (Казань, Кострома, Ярославль, Суздаль и др.). В 1868 г. напротив них были построены упомянутые «Малые ряды» купца Бакирова — одноэтажное каменное Г-образное здание, вытянутое по главному фасаду и разделенное на отдельные отсеки с арочной галереей перед ними. Со стороны Васильевского переулка на анфиладу Гостиного двора выходили фасадом магазин и склад Бакировых, наружный декор которых решён в местных традициях кирпичного узорочья. Рядом с ними, в доме №16 по Васильевскому переулку, принадлежавшем купцу Григорию Зарубину, летом 1891 г., по мнению Е. И. Скобелкина, останавливался на ночлег цесаревич Николай Александрович (будущий Николай II). Надо признать, что этот вопрос требует дополнительного исследования, т. к. у Зарубиных здесь было несколько домовладений.