Идея построить новое современное здание театра в Варне появилась еще в начале ХХ века и была связана с созданием профессиональной театральной труппы, которая нуждалась в собственном здании, поскольку одного зала "Соединение" было явно недостаточно. Однако эта идея встретила отпор со стороны некоторых общественных деятелей, считавших строительство театра преждевременным, а содержание труппы слишком обременительным для городского бюджета. Некоторое время эта тема широко обсуждалась общественностью. В 1909 г. на первом заседании городского совета новоизбранный мэр Иван Церов затронул вопрос о новом здании. Советники дали согласие на строительство. Вскоре было определено и место - в южной части городского сквера, между часами и источником с Махмудовой надписью. Фасад театра должен был выходить на площадь.

Конкурс на проект театра выиграл известный архитектор Никола Лазаров. Он является автором здания, в котором до недавнего времени располагалось варненское радио, а также Народного театра имени Ивана Вазова в Софии. По архитектуре и внутреннему оформлению здание должно было походить на софийский театр. Оно было рассчитано на тысячу мест, расположенных в партере и на двух балконах. Первоначально проект предусматривал казино и открытую сцену, но позже они были исключены из плана. 26 марта 1912 г., "во второй день Пасхи... с подобающей торжественностью был заложен первый камень в основание городского театра..." В присутствии варненской общественности восторженную речь произнес мэр Церов. После речи официальные лица и архитектор Лазаров подписали торжественный акт и поместили его в специальный каменный ящик. В основание здания положили также болгарские монеты.

На возведение театра был отведен срок в три года. Строительство развернулось сразу же, но начавшиеся в скором времени войны надолго его прервали. До 1918 г. здание оставалось незавершенным, без крыши, стройка заросла бурьяном. Были исчерпаны и средства. Зимой 1920 г. городской совет единогласно принял решение о создании профессиональной театральной труппы. Дискуссия проходила очень оживленно: "Мы не ждем прибылей от театра..." (Д.Кондов, мэр города), "Ужасно стыдно, что в Варне до сих пор нет театра!" (Кр.Мирски). 12 марта 1921 г. труппа дебютировала со спектаклем "Инстинкт" Анри Кестмекера. Эта дата считается днем рождения варненского театра. В восстановление здания театра включились все жители города. В 1922 г. был создан общественный комитет. Тема активно обсуждалась в газетах. В 1928 году мэрия объявила пятимиллионный целевой заем. "Лихорадка пожертвований" охватила варненцев: билеты фонда на строительство Варненского городского театра продавались повсюду - в булочной, кино, банях, их предлагали даже вместе с плетеными стульями в Приморском парке. Добровольные пожертвования делали и многие болгары. Меньше чем за месяц удалось собрать миллион левов... Теперь строительством занимались архитекторы Д.Дабков и Ж.Богданов. И вот: "Наконец-то, слава Богу! После долгих десятилетних превратностей здание Варненского городского театра закончено и 5 июня 1932 г. торжественно открыто", - вспоминал Иван Церов. В первый вечер на сцене была представлена пьеса "Хыши" Ивана Вазова. Первым директором был назначен Стоян Бочваров, имя которого театр носит сегодня.

Вне всякого сомнения, что архитектурным решением театра Никола Лазаров стремился приблизить Варну к крупным европейским городам. Закругленный барочный фасад здания богато орнаментирован декоративными элементами, колоннами, карнизами и скульптурными изображениями. К дверям ведет несколько ступенек, что вносит дополнительный элемент торжественности при входе в театр. Эллипсовидный вестибюль в стиле сецессион и боковые коридоры ведут к залу. По широким лестницам зрители поднимаются на балконы. Сам зал имеет классическую для театров форму подковы. Закругленные формы мягких кресел повторяют линии балконов. Самые знатные зрители занимали места в ложах у театральной сцены. Здание завершается мансардной крышей, овальным куполом над вестибюлем и четырьмя меньшими куполами над боковыми спиральными лестницами. Таким встречал своих зрителей театр около полувека.

С годами начинает остро ощущаться нехватка служебных помещений и репетиционных залов. Не уделяется достаточно внимания поддержанию здания, и оно постепенно теряет былой блеск и функциональность. Ремонт становится неизбежным, поэтому в начале 1980-х гг. принято решение реконструировать здание. Главным в реконструкции стало расширение площади здания путем сооружения служебных помещений. Прежде они располагались сбоку и за сценой. В результате объем здания увеличился в два с половиной раза. Поскольку первоначально предполагалось, что это будет лишь здание театра (а для оперы построят новое), после реконструкции оркестру приходится ютиться в неудобной импровизированной оркестровой яме. Самым значительным изменением в зале стало удаление двух первых рядов партера и одного балкона. Это позволило увеличить зал, однако при этом пришлось пожертвовать представительностью и старинным характером внутренней архитектуры. Во время реконструкции была монтирована и специальная подъемная система для декораций, современная осветительная техника с центральным пультом управления, новая климатическая установка. Реконструкция завершилась в декабре 1989 г. В целом внешний архитектурный облик здания театра сохранился таким, каким он был в день открытия. Сегодня театр - один из акцентов варненской архитектуры.