Ignacio de Figueroa y Mendieta, marqués consorte de Villamejor, vivía en 1885 en la zona antigua de Madrid, en un enorme caserón entre medianerías con un patio central y jardín interior posterior, cercano a la plaza del Progreso, en la antigua calle de Barrio Nuevo, número 12, hoy denominada Conde de Romanones. Al igual que muchos otros nobles afincados en la Corte, decidió trasladar su residencia al Ensanche, eligiendo para ello el paseo de la Castellana, la zona más privilegiada, donde los terrenos habían adquirido mayor valor y contaban con buenas comunicaciones, tanto con el centro como con el hipódromo; para ello compró el terreno del Panorama Nacional que había salido a subasta pública.
En septiembre de 1885 pidió que le fuera hecha la tira de cuerdas para la nueva construcción. Un mes más tarde, el arquitecto municipal Enrique Sánchez y Rodríguez marcó las alineaciones y rasantes a las que debía ajustarse la edificación, pero hasta dos años más tarde no se pidió la licencia para construirlo.
El proyecto de la casa-palacio presentado al ayuntamiento está firmado por José Purkiss para llevar la dirección facultativa a pesar de ser maestro de obras. El edificio consta de tres fachadas, la principal retranqueada del paseo para dejar un paso a los carruajes, la secundaria a Alcalá Galiano y la tercera dejando un paso libre entre el palacio y el hotel «Ametller» hacia las cocheras situadas en el sótano. Cuenta con planta sótano, en toda su extensión, planta baja retranqueada sobre la rasante de la calle con una escalinata de acceso y plantas principal, segunda y ático. El desmonte y paso de carruajes se iniciaron en abril de ese mismo año y al finalizar el año se empezó la construcción del palacio que no se terminó hasta diciembre de 1893.
El palacio sufrió una primera remodelación para residencia de su nuevo propietario, que lo había adquirido poco tiempo antes de la boda con Luisa María de Orleans, su segunda esposa. En él habitaron desde 1907 hasta 1914 en que trasladaron su residencia a Sevilla al ser nombrado Carlos de Borbón capitán general de Andalucía.
La nueva remodelación fue llevada a cabo por José de Espelius y Anduaga, el arquitecto de presidencia. La planta baja y primera se adaptaron para Presidencia y la planta segunda fue ocupada por la Inspección Civil de Guerra y Marina y del Protectorado de Marruecos y las caballerizas desaparecieron para dejar lugar al archivo y otras dependencias. Hay pocas referencias hasta después de la Guerra Civil. Según Ortega Rubio, en 1921 estaba establecido el Ministerio de Trabajo en el primer piso y el Directorio Militar ocupó el palacio de Presidencia. Son famosos los Consejos de Ministros presididos por Manuel Azaña en el salón de Consejos. En esta etapa sus salones fueron reformados con gran lujo, se tapizaron de seda y se decoraron con arañas, cuadros y muebles traídos del Palacio Real de Riofrío.
El arquitecto Diego Méndez fue el encargado de la conservación de la Presidencia del Gobierno desde 1955. Su primera labor consistió en una serie de reparaciones, pero en los años siguientes emprendió una serie de reformas interiores sin tocar los salones principales. Fue aprobada la ampliación de una planta que no se hizo y diez años más tarde se volvió a plantear la ampliación ante la falta de espacio. Méndez proyectó un pabellón que debía adosarse en el lado sur tomando parte del jardín del antiguo palacio Egaña, en Génova, 29, para ensanchar la biblioteca y el archivo, que tampoco se hizo. Pero la idea se retomó en los últimos años de la vicepresidencia de Carrero Blanco, instalando en el nuevo pabellón la cafetería. Los servicios de Presidencia del Gobierno habían crecido tanto que poco a poco se fueron adquiriendo otros edificios, como el Palacio de los Condes de Casa Valencia en Castellana, 5, y parte de Alcalá Galiano, 8.
A primeros de diciembre de 1976, la presidencia del Gobierno decidió, por seguridad, abandonar el palacio como sede del Ejecutivo, trasladándose al Palacio de la Moncloa, un pabellón de campo que hasta entonces operaba como museo. El traslado se hizo efectivo el 1 de enero de 1977. Tras ello se abrió un nuevo período histórico para el palacio de Villamejor, empezando una época de cambio de inquilinos y con ello se hicieron varias reformas en su interior.
En la actualidad las plantas del palacio están distribuidas en torno a un patio central rectangular, auxiliado por otros dos patios menores, localizados en la pared medianera. Tiene dos puertas de entrada, una en el eje central de la fachada principal y la segunda, en el extremo izquierdo de la fachada de Alcalá Galiano.
El aspecto exterior del palacio es simétrico y equilibrado, enmarcado dentro de la corriente ecléctica de raíz clasicista, siguiendo la línea iniciada por Emilio Rodríguez Ayuso en el palacio Anglada y desligada ya de la corriente francesa del palacio de Uceda. La composición de la fachada principal es simétrica destacando el cuerpo central que sobresale y presenta un tratamiento distinto del resto del palacio. Este cuerpo central, construido en piedra de Colmenar, está enmarcado entre pilastras y forma tres calles en donde se sitúan los tres vanos separados por columnas o pilastras adosadas dependiendo de la planta. El resto de la fachada, al igual que las otras dos, tienen un lenguaje y cromatismo común, combinando los parámetros de ladrillo con los detalles ornamentales en piedra variando la decoración por plantas y unificando todo el edificio con las impostas, la cornisa con canecillos en forma de ménsulas y la balaustrada que lo remata y enmascara el ático que está retranqueado a la segunda crujía.