Jeszcze w okresie przedwojennym pałac Mostowskich wraz z budynkiem I Oddziału Warszawskiej Straży Ogniowej górowały nad ulicą Przejazd. Dzisiaj ulica nie istnieje; dawniej trakt ten łączył Leszno z Nowolipkami, zaś po wojnie został wchłonięty przez aleję gen. Władysława Andersa. Zabudowa ulicy w dużej mierze powstała w okresie Królestwa Kongresowego, kiedy to place zapełniły się kamienicami, pałacami oraz budynkami użyteczności publicznej. W 1823 r. Antonio Corazzi przebudował dawny pałac Hilzenów, pozostający podówczas w rękach ministra spraw wewnętrznych Tadeusza Mostowskiego. Monumentalną bryłę korpusu głównego pałacu urozmaicała wielkoporządkowa kolumnada w drugiej i trzeciej kondygnacji. Ponad półokrągłymi oknami po obu stronach kolumnady umieszczono pary skrzydlatych geniuszy, wykonanych przez Aleksandra Jana Konstantego Norblina. Szczyt fasady zwieńczono rzeźbą orła. Inne dekoracje rzeźbiarskie wyszły spod dłuta pracującego w tym czasie w Warszawie Pawła Malińskiego.
Mostowski sprzedał przebudowany pałac rządowi Królestwa Polskiego na siedzibę Ministerstwa Spraw Wewnętrznych i jako minister dalej w nim mieszkał. W czasach Mostowskiego organizowano tam liczne bale i rauty, na których bywała arystokratyczna elita Warszawy i sam książę Konstanty. Po powstaniu listopadowym Mostowski znalazł się na emigracji; mieszkał kolejno w Berlinie i Paryżu. W tym czasie pałac został zajęty przez administrację rosyjską, z fasady usunięto orła. Najprawdopodobniej w latach 60. XIX w. w obiekcie umieszczono rosyjski Wołyński Pułk Piechoty Lejbgwardii, wchodzący w skład 3 Dywizji Piechoty Gwardii. W gmachu mieściło się też muzeum pułku.
Po odzyskaniu niepodległości do pałacu wprowadzono Dowództwo Okręgu Korpusu nr I. Po wojnie podjęto prace związane z odbudową obiektu, którą zrealizowano według projektów Zygmunta Stępińskiego. Zdjętego po powstaniu listopadowym orła przywrócono dopiero w 2006 r.
