С улицы Ленина здание театра кукол похоже на сказочный терем: приземистый объём, а над восточной частью поднимается гранёный шатёр. Название объясняют этой формой, хотя театр старше своего дома почти на 30 лет: он появился в 1937 году и первые годы играл в других стенах. Имя прижилось и стало официальным.
Основал театр Ананий Васильевич Бадаев, художественный руководитель Вологодского театра юного зрителя. Он собрал труппу и начал показывать кукольные спектакли детям. С 1941 по 1943 год театр выезжал на фронты: артисты играли для бойцов, а не только для школьных залов. Позже, уже в мирные годы, «Теремок» сам принимал гостей — в 2000 году провёл в Вологде «Вологодскую потеху», смотр кукольных театров России.
Своё нынешнее здание театр занял в 1966 году. Это бывшая церковь Зосимы и Савватия Соловецких, построенная в 1759–1773 годах в формах барокко: двухэтажный храм с трапезной и восьмигранной колокольней. Место старое: деревянная церковь на нём упоминается в писцовой книге 1627 года, а каменный храм принадлежал Соловецкому подворью — хозяйственному двору монастыря в городе. В 1928–1929 годах церковь закрыли, устроили клуб печатников и металлистов «Красный луч», снесли колокольню и главу. Позже здесь работала филармония, а перед приходом театра здание перестроил архитектор Владимир Баниге: пристройку в неорусском стиле лишили декора, над алтарной частью подняли шатровое покрытие. Отсюда и силуэт, похожий на терем.
В репертуаре больше 30 спектаклей для детей — от «Гуси-лебедей» до «Дюймовочки». Афиша рассчитана на разный возраст: «По щучьему велению», «Золушка» Шварца, «Сказка о царе Салтане». Но кукольный театр не всегда остаётся детским: за годы здесь поставили 8 спектаклей для взрослых, и один из них, «Кармен» по Мериме, получил «Золотую маску» в 2014 году. С этой работой театр объехал фестивали в Загребе, Суботице и Которе. Есть в репертуаре и «Теремок» Маршака — сказка, давшая имя театру.
Гастролировал «Теремок» и за границей: в Венгрии, Болгарии, Финляндии, где играл на языке принимающей страны. У театра есть собственные привычки: газета «Теремоша», абонементы для школьников, экскурсии по закулисью. В 2018 году «Теремок» получил премию Правительства России имени Фёдора Волкова — за вклад в театральное искусство.
В зале нет иконостаса, зато есть сцена, а над ней — своды, которым больше двух с половиной веков. Дом сменил 3 назначения — храм, клуб, театр, — и каждый раз его узнают по одному и тому же силуэту.