В 1781 году А. А. Безбородко, возглавлявший в числе других учреждений и Почтовый департамент, приобрел два каменных дома близ Почтамта — подворье Курского Знаменского монастыря на углу Выгрузного переулка (ныне Почтамтский переулок) и смежный с ним дом «танцовалыцика» Топоркова, построенный в 1756 году. Безбородко объединил дома и создал дворец, сравнительно скромный по своему внешнему облику, но великолепно отделанный внутри. При перестройке домов были сохранены их стены и частично внутренняя планировка.
Чертежи домов утрачены, но ясное представление о них дает аксонометрический план Петербурга 1760-х годов.
Оформление интерьеров, выполненное по чертежам Д. Кваренги в 1780-х годах, частично сохранилось. Интересно убранство вестибюля, лестницы, овального зала с зелеными колоннами и аванзала, где сохранились росписи плафонов и отделка искусственным мрамором. Танцевальный зал с коринфскими колоннами, росписью плафона и лепными украшениями — один из лучших образцов архитектуры интерьера русского классицизма. В 1829 году здание было приобретено Почтовым ведомством. В 1870-х годах фасады дворца, решенные в формах русского классицизма, получили новую декоративную обработку в характере ренессанса, значительно изменившую их первоначальный облик. От старой композиции сохранились центральный портик из четырех гранитных колонн и размещение оконных проемов.