Se alzaba en la actual calle de las Angustias, frente a la iglesia penitencial de esta advocación, edificada en este lugar muchos años después que el palacio. Ocupaba toda la parcela que hoy alberga el Teatro Calderón, la calle de Alonso Berruguete y los edificios de los números 3 y 5 de la calle de las Angustias, teniendo delante de sí una gran explanada, formando una plaza, conocida como plazuela del Almirante. Por su parte trasera daba frente al palacio del Marqués de Villasante, hoy Palacio Arzobispal.

Su fachada principal era sencilla y uniforme, compuesta de dos pisos: el bajo con rejas de hierro y el segundo con balcones, con un ajimez gótico; a los costados tenía dos torreones salientes en forma de martillo.

Fue morada de Fernando el Católico y su segunda esposa, Germana de Foix, y en sus aposentos nació el 3 de mayo de 1500 su hijo Juan de Aragón, quien murió en este mismo palacio a las pocas horas. Sus restos mortales fueron sepultados inicilamente en la iglesia conventual de San Pablo vallisoletana, para ser trasladados al poco tiempo al monasterio de Poblet, en Cataluña.

En el contexto de la guerra de las Comunidades de Castilla, en la que la comunidad de Valladolid tuvo una actividad destacada, el almirante de Castilla Fadrique Enríquez de Velasco como capitán general de los ejércitos realistas de Carlos I, concedió un indulto o perdón general en nombre del monarca a los comuneros el 27 de abril de 1521, apenas unos días después de la batalla de Villalar. Su publicación fue acompañada de gran aparato y música de trompetas y otros instrumentos guerreros en la Plaza Mayor, en la plaza de Santa María y en la plazuela Vieja, sita a continuación de este palacio en dirección hacia la iglesia de San Pablo.

En 26 de agosto de 1522, Carlos I acudió a Valladolid y confirmó el perdón otorgado por el almirante, exceptuando solamente algunas de las personas que más directamente influyeron en el levantamiento. En agradecimiento a la participación del almirante, los vecinos de Valladolid colocaron sobre la puerta principal de su palacio una gran lápida de mármol negro con la siguiente inscripción:

«Viva el Rey con tal victoria,

Esta casa y su vecino,
Quede en ella por memoria,
La fama, renombre y gloria,
Que por él a España vino.
Año M. D. XXII, Carlos.

Almirante Don Fadrique, segundo de este nombre».

Según afirma Ventura Pérez en su Diario de Valladolid, «en 3 de septiembre de 1764 murió en el palacio del Almirante D. Ignacio Pimentel, conde de Luna, hijo del conde de Benavente. Se había venido a vivir allí poco más de un mes por haber recaído en él los estados que corresponden a aquella casa».

Entre 1850 y 1856 el palacio sirvió de sede para la Diputación de Valladolid. La lápida conmemorativa del almirante fue cubierta con una capa de yeso, sobre la que se pintó la inscripción: "Diputación Provincial".

Pasó a ser propiedad particular de Diego Morales, quien lo vendió en 1863 a la sociedad constructora del Teatro Calderón. Su derribo comenzó el 1 de junio de ese mismo año. Varios ladrillos, azulejos y piñas invertidas estalactíticas que formaban parte de su construcción o adornaban sus dependencias fueron llevadas al Museo de Valladolid.

En el nuevo Teatro Calderón, en la esquina que da a la calle de Leopoldo Cano, se colocó la siguiente placa en 1924:

•   Partes de este artículo incluyen texto de Valladolid, sus recuerdos y sus grandezas: religión, historia, ciencias, literatura, industria, comercio y política (1902), una obra de Casimiro González García-Valladolid en dominio público.
• González García-Valladolid, Casimiro (1902). «Palacio del Almirante». Valladolid, sus recuerdos y sus grandezas: religión, historia, ciencias, literatura, industria, comercio y política 1. Valladolid: Imprenta de Juan Rodríguez Hernando. pp. 601-604. Wikidata Q131116998. Consultado el 7 de septiembre de 2020.