Решение о строительстве гостиницы на главной площади города, в то время называвшейся площадью 20-летия Октября, было принято исполкомом Воронежского горсовета в январе 1939 года. Строительство 5-этажной гостиницы на 250 номеров по проекту архитектора П. Н. Твардовского велось с 1939 года по ноябрь 1940 года. Во время оккупации Воронежа здание было сильно разрушено. На одном из балконов гостиницы 25 января 1943 года солдаты 60-й армии и генерал И. Д. Черняховский водрузили знамя Победы. Само здание восстановили к 1951 году по проекту архитектора А. В. Миронова при участии П. Н. Твардовского.
Здание композиционно объединено с примыкающим к нему пятиэтажным жилым домом. На стыке улиц здание имеет небольшую башню с часами на три стороны (установлены в 1986 году). Изначально башню завершала надстройка в виде беседки, но в 1986 году верх башни украсил металлический шпиль, на вершине которого — парусник, символизирующий роль Воронежа в истории создания военно-морского флота. Угол здания гостиницы выделен мощными пилястрами высотой в 3 этажа с коринфскими капителями.