El palacio, considerado uno de los edificios civiles más antiguos de la ciudad, fue construido a principios del siglo XIV por Nuño Pérez de Monroy,^[2]​ abad de Santander de la Casa de Monroy, familia noble placentina a la que en aquella época se le había concedido el señorío de Monroy, localidad que cuenta con un castillo de la misma época que este palacio.^[3]​^[4]​ En este palacio nació doña María Rodríguez de Monroy "la Brava", quien en 1465 vengó la muerte de sus hijos en Salamanca (donde vivía y donde se conserva su casa), persiguiendo a sus asesinos hasta Viseu y haciéndoles decapitar.^[5]​

El palacio ha sido testigo de momentos clave en la historia de Plasencia, desde el encumbramiento de los Monroy como una familia aristocrática medieval hasta su declive. Esto incluye la partida de los Monroy de la ciudad debido al dominio de la Casa de Zúñiga, lo que marcó un punto de inflexión en la historia del palacio

Cuando en el siglo XV la ciudad fue entregada por Juan II a la Casa de Zúñiga, el palacio fue vendido por los Monroy a la casa noble Carvajal, quienes pasaron a ser la familia más influyente de la ciudad tras apoyar militarmente a los Reyes Católicos en la restauración del realengo placentino. Debido a ello, en las décadas posteriores se albergaron en este palacio importantes personalidades de la época, como el rey Fernando el Católico, el cardenal Bernardino López de Carvajal y Sande y el santo franciscano Pedro de Alcántara.^[3]​

Durante su estancia en Plasencia en octubre de 1488, el rey Fernando el Católico se hospedó en la Casa de las Dos Torres como invitado de Francisco de Carvajal. En honor a los servicios prestados, el monarca ordenó colocar el escudo de los Carvajal sobre la Puerta de Trujillo por la que había accedido a la ciudad.^[6]​

San Pedro de Alcántara también se alojó en la misma sala que el rey, una estancia de seis metros cuadrados en la torre suroccidental, ya desaparecida. La tradición recoge que fue visto levitando en oración por miembros de la familia Carvajal.

El palacio contaba con jurisdicción propia, simbolizada por los leones en altorrelieve de su portada, que representaban el derecho de asilo y otras prerrogativas legales.

Durante el Renacimiento, la casa experimentó su máximo esplendor, siendo un ejemplo del apogeo arquitectónico de la nobleza de la ciudad. Se realizaron múltiples reformas y ampliaciones que la convirtieron en un importante centro de poder.

El edificio posee una estructura compleja que abarca múltiples reformas desde el siglo XIII hasta el siglo XX, combinando los estilos gótico, renacentista y modernista. La parte más antigua es su torre, del siglo XIII, que muestra en su parte más alta el escudo de la familia Carvajal; el palacio se estructuraba antiguamente entre esta torre y una segunda en su otro extremo, debido a lo cual se conoce como "Casa de las Dos Torres", pero la segunda torre fue gravemente dañada en el terremoto de Lisboa de 1755 y hubo que derribarla en el siglo XIX por seguridad. La parte más conocida del edificio es su fachada, reformada en el siglo XIX con vanos neogóticos; sin embargo, esta fachada conserva la portada original gótica con los altorrelieves de dos leones.^[3]​^[4]​^[7]​

El edificio sufrió graves daños durante la Guerra de la Independencia y fue utilizado como hospital para los enfermos del Ejército de Castilla, lo que contribuyó a su estado de deterioro. A causa de las deudas acumuladas tras la Guerra de la Independencia, la Casa de las Dos Torres fue vendida en subasta pública en 1817. Originalmente tasada en más de 250.000 reales, su precio se redujo drásticamente a entre 30.000 y 35.000 reales debido a los destrozos sufridos.

El registro de escrituras de la propiedad indica que en 1817, la casa fue comprada por Félix Luis Prieto Chamorro, en un estado muy deteriorado, lo que marcó el inicio de la transición hacia otros propietarios, antes de que llegara a manos de la familia Sánchez-Ocaña.

Entre 1912 y 1920, la torre sur del palacio fue derribada durante unas obras dirigidas por el arquitecto Francisco Mirón. El entonces propietario, Juan Sánchez-Ocaña y Clavijo, permitió la demolición por motivos de seguridad, aunque algunos cronistas creen que no era necesaria. Con ello, la casa perdió su aspecto original de “dos torres”

El palacio fue habitado por la familia Sánchez-Ocaña, quienes jugaron un papel en la conservación parcial del edificio y cuya historia se entrelaza con la decadencia y posterior intento de revitalización de la casa en épocas recientes.

El Plan General Municipal de Plasencia de 2015 protege el edificio como monumento de relevancia local.^[7]​ Pese a su importancia histórica, el edificio llegó al siglo XXI abandonado, deteriorado y repartido entre varios propietarios. En los primeros años del siglo se intentó rehabilitar el palacio para destinarlo a restaurante y oficinas, pero la grave crisis económica de la época hizo fracasar el proyecto que no estuvo exento de polémica ya que se intentó reconstruir la torre derribada en el terremoto de Lisboa. Tras una fuerte polémica, que duró años, finalmente se autorizó la reconstrucción de la torre en acero corten, cosa que finalmente no se llevó a cabo.

En 2020, sus propietarios presentaron al Ayuntamiento de Plasencia un proyecto para consolidar la estructura, con previsión de destinarlo a viviendas.^[8]​^[9]​^[10]​Esto obligó a realizar complejas obras de consolidación del edificio, incluyendo el vaciado del edificio, y completo cambio de forjados y cubierta que concluyeron en 2022.

En la actualidad el edificio pertenece a un empresario madrileño, nieto de los Sánchez-Ocaña, antiguos propietarios del palacio, que a lo largo de la última década ha ido adquiriendo las partes del edificio que no poseía, consolidando la propiedad.