Został zbudowany w latach 1762-1765 na miejscu parterowego dworu z dziedzińcem, należącego uprzednio do rodziny Paców. Wzniesiony w stylu barokowym dla wojewody mińskiego Jana Augusta Hilzena. W 1795 r. w drodze spadku stał się własnością Tadeusza Mostowskiego - późniejszego ministra spraw wewnętrznych.
Następnie pałac został kupiony przez rząd Królestwa Polskiego. W latach 1823-1824 został poddany przebudowie na podstawie proj. Antonia Corazziego w stylu klasycystycznym z dekoracjami rzeźbiarskimi autorstwa Pawła Malińskiego i J. A. Norblina. Budynek stał się siedzibą Komisji Rządowej Spraw Wewnętrznych i Policji. Koncertował w nim także kilkakrotnie Fryderyk Chopin.
Po upadku powstania listopadowego pałac pozostał we władaniu resortu spraw wewnętrznych. W związku ze zniesieniem autonomii Królestwa Polskiego ok. 1867 r. Komisja została rozwiązana, a budynek tymczasowo przekazano na siedziby różnych instytucji cywilnych m.in.: Banku Handlowego. W I poł. lat 70. XIX w. pałac został ponownie przebudowany i przekształcony na koszary Wołyńskiego Pułku Lejbgwardii.
Bezpośrednio po odzyskaniu przez Polskę niepodległości w listopadzie 1918 r. pałac był przejściową siedzibą różnych inspektoratów wojskowych i departamentów Ministerstwa Spraw Wojskowych. W latach 1921-1939 znajdowało się tu Dowództwo Okręgu Nr 1.
W czasie powstania warszawskiego w 1944 r. obiekt został zniszczony przez Niemców.
Z zagłady wojennej ocalały jedynie partie południowej elewacji z portykiem. W latach 1948-1951 został odbudowany wg projektu Zygmunta Stępińskiego z wprowadzeniem wielu poważnych zmian i uproszczeń. Ich wprowadzenie wiązało się z brakiem oryginalnej dokumentacji projektowej, która uległa zniszczeniu podczas walk powstania warszawskiego.
Budynek przeznaczono na siedzibę Komendy Milicji Obywatelskiej m. st. Warszawy. Od 1990 r. znajduje się tu Komenda Stołeczna Policji.