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