У 1883 році з ініціативи Херсонського генерал-губернатора О. С. Ерделі на засіданні Міської Думи вирішено було розпочати у Херсоні будівництво нового приміщення театру. Проєкт здійснив архітектор Владислав Домбровський. 

Для побудови Херсонського міського театру було вибрано місце на Старообрядницькому майдані, який був на той час занедбаним пустирем. Перший камінь був закладений 18 квітня 1884 року. 28 вересня 1889 року комісія в присутності будівельників театру та архітектора Домбровського «провела детальне обстеження і визнала його збудованим міцно та цілком задовільно». 

1 жовтня о 12 годині відбулось урочисте освячення театру в присутності начальника губернії, віце-губернатора та членів Міської Думи. Після закінчення богослужіння ключі від нового театру були передані Міському Голові В. Г. Терещенку, який «кількома словами подякував будівельнику театру – архітектору Домбровському, завдяки якому театральна будівля виявилася цілком витонченою, зручною та місткою. Потім щиро подякував Херсонському губернаторові за надане Його Високопреосвященством сприяння в облаштування театру».

Того ж дня о 8 годині вечора було влаштовано першу виставу. «Уся простора театральна зала від верху донизу була переповнена публікою, але аж ніяк не могла вмістити всіх охочих… тож виставу… повторили ще й 2-го числа…». У день відкриття артист О. І. Шадурський прочитав авторські вірші, написанні на честь Херсонського театру.

У другому театральному сезоні (1891–1892 рр.) очолював трупу В. І. Власов. Він поставив декілька маловідомих комедій та старовинних мелодрам, а у середині сезону із запрошеними артистами показав «Циганського барона». Зборів не було. Творчий колектив розпався. 

З 1892 і до кінця століття театральне приміщення перетворилося на майданчик для гастролерів. Найбільшим успіхом у херсонців користувалися колективи М. Кропивницького, братів Тобілевичів (І. Карпенко-Карий, М. Садовський, П. Саксаганський) та їхньої сестри М. Садовської-Барілотті. Всі вони були уродженцями Херсонської губернії.