La construcción de este palacio se inició en 1776 por encargo de Carlos III como residencia primer secretario de Estado, con la intención de crear un centro del poder político junto con el Palacio Real. Esta labor le fue encomendada al arquitecto preferido del rey, Francesco Sabatini, también responsable del diseño y construcción de las caballerizas del Palacio Real, que estaban situadas al otro lado de la entonces calle Nueva, hoy calle Bailén.
Aunque el secretario de Estado cuando se inició la construcción del palacio era el Marqués de Grimaldi, el primero en ocuparlo fue el Conde de Floridablanca ya en 1782, que residió en él durante 10 años.
Su ocupante más conocido, ya con Carlos IV, fue Manuel Godoy, que en 1792 lo adquirió, amplió y reformó para usarlo como residencia particular. Fue entonces cuando pasó a conocerse como Palacio de Godoy. Esta fue época de mayor esplendor del palacio, según relatan los numerosos testimonios que describen la lujosa y agitada vida que albergaba.
En 1807, año en que Godoy recibe el Palacio de Buenavista como regalo del Ayuntamiento de Madrid, vende de nuevo a la Corona el edificio proyectado por Sabatini, que pasó a ser la sede del Consejo del Almirantazgo. No obstante, se reserva la propiedad de sus habitaciones, ubicadas en la zona que daba a la calle Bailén. Al poco tiempo se produce el motín de Aranjuez, Godoy cae en desgracia y se le incautan todos sus bienes.
Cuando en 1808 los franceses entran en España, sirvió de residencia al comandante del ejército francés y gobernador de Madrid, Joaquín Murat, quien, en su retirada, se lleva gran parte de sus bienes y enseres. Ya en 1819, tras la guerra, el palacio albergó la sede de la Biblioteca Real. Posteriormente fue ocupado por las Secretarías de Gracia y Justicia, Guerra, Marina y Hacienda, por lo que en esa época se lo conocía como Casa de los Ministerios.
En 1846, un incendio destruyó gran parte del inmueble. El percance obligó a trasladar varias secretarías, de modo que solo permaneció la de Marina. Precisamente el hecho de que la sede del Almirantazgo primero y la Secretaría de Marina después se mantuviesen en este edificio durante tantos años es lo que da nombre a la plaza en la que se ubica: plaza de la Marina Española.
Cuando el Ministerio de la Marina abandonó el palacio en 1929 se llevó el despacho de Godoy con los frescos incluidos, el bajo relieve de la escalera, los faroles que la adornaban y unos tondos pintados por Goya. No obstante, el mayor deterioro se produce en 1931, cuando se derriba aproximadamente un tercio del palacio para ensanchar la calle Bailén, precisamente el ala en la que se ubicaban las dependencias personales de Godoy.
En años sucesivos albergó el Museo Naval, el Museo del Pueblo Español y el Centro de Estudios Políticos. En 1962 fue declarado Monumento Histórico-artístico y Bien de Interés Cultural en el año 2000.