История Воронежского театра кукол официально началась 8 октября 1925 года и связана с именем основателя театра Н.М. Беззубцева — директора Музея изящных искусств Воронежского государственного университета (ВГУ), сотрудника губернского музея. Первое кукольное представление в Воронеже состоялось в 1925 году в зале Воронежского государственного университета, на базе которого театр работал несколько лет. 5 ноября 1930 года театр кукол ВГУ вошёл в состав вновь созданного профессионального театра. В этот же день Н.М. Беззубцев был арестован по «делу краеведов».
В 1930-х годах были поставлены спектакли: «Юкки и Лол» Ю.А. Гауша, «Похождения Петрушки в стране лентяев» М. Данилевского, «Каштанка» по А.П. Чехову, «Джим и доллар» А.П. Глобы, «Сказка о рыбаке и рыбке» и «Сказка о мертвой царевне и семь богатырях» по А.С. Пушкину.
В 1937 году театр подразделялся на театр Петрушки и театр марионеток. По воспоминаниям Г.Д. Лесных, в 1940-е годы театр много гастролировал, перевозя театральный скарб на тележке, а после войны — на полуторке. Сотрудники театра делали кукол сами. В 1942 году здание театра было разрушено, утрачена личная библиотека и коллекция кукол Н.М. Беззубцева. Артисты-кукловоды ушли на фронт.
В 1944 году Воронежский кукольный театр возобновил свою работу и вошёл в сеть государственных театров. В составе труппы работали: Н.В. Деленч-Ленчовская, Т.И. Августина, З.И. Августина, Ф.И. Балашов, М.И. Григорова, П.И. Фетисов, Ю.П. Соловьева. Среди постановок: «Кот в сапогах» по Ш. Перро, «Сказка партизанского леса» В. Швенбергера, «Несносный слоненок» по Р. Киплингу.
В 1950-е годы главным режиссёром театра был А.С. Чертов, поставивший спектакли: «Финист — ясный сокол» и «Иван — крестьянский сын» по мотивам русских народных сказок, «Мальчик из Кияж озера» Л.Т. Браусевич, «Лесные артисты» Н.В. Гернет, «Мистер Твистер» С.Я. Маршака.
Среди лучших спектаклей 1960–1970-х годов: «Божественная комедия» И. Штока, «Военная тайна» А. Гайдара. В 1969–1985 годах в театре главным режиссёром был И.Н. Лукин (1940–1988).
10 декабря 1975 года общественность Воронежа отмечала 50-летие театра кукол. В 1984 году у театра появилось новое здание. За его архитектурный проект Н. Топоев, А. Фролов, скульпторы Э. Пак и И. Дикунов были удостоены Государственной премии РФ.
С 1987 по 2003 год художественным руководителем Воронежского театра кукол «Шут» работал выдающийся режиссёр и театральный деятель В.А. Вольховский. В память о нём в 2003–2004 годах были поставлены спектакли «Королевский стриптиз», «Винни Пух и все, все, все», «Пионовый фонарь». В 2004 году на здании театра открыта мемориальная доска, увековечивающая имя В.А. Вольховского, а с 2009 года театр носит его имя.
С 1988 года театр активно и успешно гастролирует по России и за рубежом, участвует в международных фестивалях кукольных театров.
С 2005 по 2015 год художественный руководитель театра — режиссёр В.К. Козловский. В репертуаре театра есть спектакли как для взрослых («Шинель» Н. Гоголя, «Хитроумный идальго» М. де Сервантеса, перевод Д. Вассермана; «Каштанка» А. Чехова, «Пионовый фонарь» С. Энтё и др.), так и для детей («Волшебная лампа Аладдина» Н. Гернет, «Солнышко и снежные человечки» А. Веселова, «Белоснежка и семь гномов» О. Табакова, Л. Устинова и др.). В наши дни славу и популярность театру создают мастера кукольного дела: художники А. Ечеин, Е. Луценко; режиссёр Е. Шевченко; артисты Т. Ечеина, Е. Киселёва, М. Мальцев и многие другие.
Сегодня в театре ежегодно выпускаются 4-6 премьерных спектаклей. В текущем репертуаре насчитывается 48 постановок, включая два уличных спектакля. Театр сотрудничает с ведущими российскими и зарубежными режиссёрами и художниками, отмеченными профессиональными премиями. Среди них: Р. Кудашов, Е. Ложкина-Белевич, Л. Фёдорова, С. Озерская, А. Запорожский, М. Завьялова, Н. Бакулева. Коллектив регулярно участвует в международных фестивалях театров кукол, становится лауреатом и призёром престижных премий, в числе которых Премия имени Ф. Волкова и региональная театральная премия «Браво».
Активно развивается образовательная программа, включающая мастер-классы, экскурсии, просмотр архивных видеозаписей спектаклей, а также творческие встречи и обсуждения. Отдельный цикл мероприятий был посвящён 85-летию со дня рождения В. Вольховского.
Театр поступательно внедряет инклюзивную среду. В ноябре 2023 года состоялась премьера постановки «Мы так похожи: Звуки вокруг нас», ориентированной на детей с особенностями развития и ограниченными возможностями здоровья, а также на маломобильных граждан (спектакль проводится в фойе первого этажа). С сентября 2024 года запущен проект для глухих и слабослышащих зрителей, предоставляющий возможность просмотра спектаклей с сопровождением титров.