Перша будівля театру з’явилася в місті У 1840 році завдяки пруському підданому Івану Міллєру. Це був його власний будинок, розташований на розі Московської і Нікольської вулиць, куди залюбки ходила миколаївська публіка, хоча і називали її між собою «караван сараєм». Приміщення не відповідало технічним умовам для публічних закладів, тому театр вимушений був припинити свою діяльність.
В 1875 році військовий губернатор Миколаєва Микола Аркас наполягав на необхідності побудови нового театру, який відповідав би всім вимогам. Грошей у місто не було, тому ініціатива підприємця Карла Монте побудувати театр була підтримана. Нова спеціалізована будівля театру була зведена в 1881 році. Глядацька зала театру складалася з 350 місць партеру і амфітеатру, 36 лож бенуара і бельетажу, галереї. Меблі для театру виписали з Відня. Керував будівництвом автор проекту інженер Теофіл Брусницький.
Театр побудований у стилі псевдоренесансу, має елементи еклектики і модерну. Споруда прикрашена архітектурними прийомами: лоджією по фасаду на Адміральській вулиці, навісом біля входу і аттиком над ним, балюстрадою по кромці даху з вазами, встановленими на тумбах. Вікна обрамлені напівколонами, в нішах встановлені скульптури античних муз. Стіни оброблені рустом. Будівлю доповнював невеликий дворик типу курдонера, обрамлений з боку вулиці гратами.
У 1894 році театр придбав купець Яков Шеффер. Новий власник у 1898 році здійснює перебудову споруди: збільшено глядацьку залу, по-новому обладнано сцена, збудоване додаткове фойє, замість галереї – гальорка. Театр став вміщати 1310 глядачів.
З початком революції 1917 року будівлю театру використовують для різноманітних зборів. У 1920 році театр названо ім’ям наркома просвіти Анатолія Луначарського, у 1926 році, після ремонту і відновлення роботи – ім’ям наркома освіти Миколи Скрипника, в 1939 році - театр отримав ім’я льотчика-випробувача Валерія Чкалова, яке носив до 1994 року. Звістка про початок Другої світової війни застала колектив театру на гастролях у Полтаві. А 2 серпня 1941 року вийшла Постанова Виконавчого комітету Миколаївської обласної ради депутатів трудящих №3143 про евакуацію театру на Урал.
У зв’язку із неможливістю розмістити театр на Уралі, по приїзду до Свердловська колектив розформували. театр припинив своє існування. але завдяки наполегливості художнього керівника Леоніда Луккера та ініціативної групи колишніх працівників, роботу театру поновлено у 1942 році в місті Алапаєвську Свердовської області.
За 27 місяців перебування на Уралі колектив театру випустив 27 прем’єр, зіграв більше 400 вистав. 216 концертних програм було показано у військових частинах, шпиталях. У складі концертних фронтових бригад артисти виїжджали на передову. Колективом театру було зібрано кошти на побудову літака «Миколаївський театр Чкалова».
У Миколаїв колектив повернувся у 1944 році. Будівля театру після пожежі знаходилася у аварійному стані. В 1946 році її відбудували полонені німці. Споруду не лише відновили, але й значно удосконалили. До неї біля входу прибудували шестиколонний портик з важким фронтоном на рівні даху, змонтували нову сцену з обертовим кругом, переобладнали закулісну частина, з’явився третій ярус лож.
В середині 2000 років розпочався новий етап відродження і реконструкції приміщення театру. Роботи по оновленню велися з дотриманням архітектурних норм ХІХ ст., щоб не нашкодити стилістично оновленому храму мистецтва.
В 2018 році під керівництвом нового директора-художнього керівника Артема Свистуна відкрито сценічний майданчик на театральному подвір’ї, малу та камерні сцени. В 2020 році - створено інтерактивний музей театру.
Сьогодні театр є одним із улюблених місць культурного відпочинку містян і гостей Миколаєва.
