
Na místě současného raně klasicistního paláce stávaly ve 14. století tři středověké domy. S jejich sjednocením začal po roce 1702 František Ferdinad hrabě Berchtold z Uherčic. Sjednocení však dokončil až Václav Ignác hrabě Deym ze Stříteže po roce 1721. Palác poté vlastnili Malovcové z Malovic a Kinští. V roce 1800 palác koupil Josef hrabě Vratislav z Mitrovic, který jej nechal (v blíže nedoloženém roce, jistě však před rokem 1821) zásadně přestavět I. E. Palliardim. Roku 1845 koupila palác vdova Josefína kněžna Schwarzenberková z orlické větve rodu. V té době palác již nesloužil majitelce k bydlení, byl pronajímán ke komerčním účelům. V jižním křídle byla v roce 1928 zřízena pošta, která zde funguje dodnes. V roce 1948 byl palác zkonfiskován a sloužil diplomatickým službám.