Місце для будівництва театру було виділено міською управою 18 липня 1865 року зі стягненням у міський прибуток 76 рублів. Заключний висновок будівельного відділення про розгляд плану забудови місця театром з двома флігелями видано 27 серпня 1865 року. Креслення, виконані Г. Трамбицьким, затверджені 31 серпня 1865 року. Цього ж року інженер-полковник Г. Трамбицький за 76 рублів купив у міській управі ділянку землі, на які власним коштом і збудував Зимовий театр. Офіційне відкриття відбулося 1867 року. О. Пашутін в «Історичному нарисі м. Єлисаветграда» повідомляє, що перша вистава у новозбудованому театрі відбулася під час Георгіївського ярмарку наприкінці квітня 1867 року. «У новозбудованому 1867 року полковником Трамбицьким постійному кам'яному театрі перша вистава була дана трупою Виходцева, який прибув до Єлисаветграда на Георгіївський ярмарок».

У театрі Г. Трамбицького, до влаштування 1874 року театральної сцени в Громадському зібранні, ставилися українські та російські вистави аматорських труп, в яких виступали майбутні основоположники українського професійного театру М. Кропивницький, І. Тобілевич. Сам М. Кропивницький кілька сезонів працював у трупі Г. Виходцева, але чи брав він участь у першій виставі новозбудованого театру – невідомо. Це був перший кам’яний стаціонарний театр м. Єлисаветграда побудований у стилі класицизму з вкрапленням елементів декоративного бароко.Компактний двоповерховий прямокутний корпус поєднувався з двома одноповерховими малогабаритними флігелями, що у плані надавало споруді форму хреста. Внутрішнє планування, зазначає К. Шляховий, складалося з коридорів та анфіладних кімнат, які з трьох сторін прилягали до центрально розташованої великої прямокутної зали системою наскрізних входів та протипожежних маршів між поверхами.Головний вхід мав три арочних портали з чотириколонним портиком тосканського ордеру, який тримав відкритий балкон з кованим металевим парапетом. Портик класично акцентував центральну частину фасаду, який над вінцевим карнизом завершувався високим бароковим фронтоном. Тімпан фронтону був прикрашений рельєфною театральною емблемою та трьома прямокутними фільонками з ліпними гірляндами. Передні кути будівлі акцентувалися ризалітами, які завершувалися аттиками, рельєфно оздобленими ампірними вінками у прямокутних фільонках. Архітектурна пластика головного фасаду підкреслювалася скульптурною групою на вершині та декоративними вазами на краях фронтону.

Прямокутні класицистичні амбразури вікон і дверей створювали ритм урочистості обох поверхів. Дверні полотна були членовані фільонками та оздоблені різьбленням. Інтер’єри театру також мали стильові риси класицизму з окремими декоративними мотивами бароко. Чотири ошатних яруси були розподілені колонками з капітелями, бар’єри ярусів оздоблені позолоченими орнаментальними композиціями, еліптичний плафон глядацької зали гармонізував простір над розкішною кришталевою люстрою.

Ось як згадує про інтер’єр і екстер’єр театру Дон-Амінадо (А. Шполянський – видатний поет-сатирик і прозаїк, 1888-1957):«Театр був пофарбований у яскраво-рожевий колір, на фронтоні золотими літерами так і було накреслено Храм Мельпомени. А під цим пояснення: театр відставного ротмістра Кузміцького. Чотири колони підтримують фронтон; праворуч – вхід для публіки; з лівого боку – свята святих: вхід для артистів. Усередині театру все було як треба. І вестибюль, і довге фоє, і біля кожного внутрішнього входу до зали – непроникні контролери, у провінції їх називали білетерами. І, нарешті, самий зал. Боже, з яким трепетом входили ми до храму мистецтва!І як знали напам'ять усі ці ложі бенуару, бельетажу, директорську ложу та всі крісла першого ряду, на яких біліли ретельно виписані картонки…». «Ложі та крісла були оббиті потертим від часу темно-червоним плюшем, з обов'язковою бахромою, що відливала чарівним блиском гасових ламп під молочними абажурами. Але центром тяжіння була, звичайно, завіса, у важких, запорошених складках, теж весь із темного червоного оксамиту, із золотими кистями з боків і з візерунково виведеним на всю довжину багатонадійним висловом: «Сльози облагороджують душу»… Однак, що ж казати, попри своє кавалерійське минуле, відставний ротмістр, був, мабуть, глибоко художньою натурою, і знав, з чим що їдять. Все в цьому безперечному храмі було спритно і тонко обдумано. І знаменита люстра, що спускалася в лірах і амурах і вежа – райок – гальорка».

Упродовж свого існування театр зазнав багато ремонтів, а також кілька значних переробок, остання з яких призвела до повної втрати первісного вигляду інтер’єрів та суттєвої зміни зовнішніх форм. Театр було перероблено до невпізнання. Закладення колон портику знеособило головний вхід і зробило передній фасад маловиразним.

Справжню відбудову і реконструкцію цього історичного приміщення зробили у 2011-2012 рр. Завдяки титанічним зусиллям Голови Кіровоградської державної обласної адміністрації Сергія Миколайовича Ларіна, відбулося небачене будівництво, що подарувало місту та Україні красень-театр, чудо духовного храму. Сьогодні, після реконструкції, театр повертається до своїх першовзірців. Сцена, що бачила виступи акторів світового значення, і сьогодні збирає численне коло прихильників та шанувальників. Після відбудови і реконструкції мистецьке життя ще яскравіше завирувало на сцені, в залі та поза стінами будівлі, а також і на Театральній площі.