Fue castro del Imperio cuando Turgalium era prefectura emeritense. Crujió en las guerras de Leovigildo contra los Suevos y su hijo San Hermenegildo. Se entregó a las tropas islámicas de Musa en el año 713. Antes de finalizar el siglo VIII Carlomagno tomó esta fortaleza según el "Codex Calistinus". Abd al-Rahman III nombra gobernador en Torjala. En 1165 fue conquistado por el portugués Gerardo Sempavor que hubo de volverlo a Fernando Rodríguez de Castro en 1169. Fue cristiano hasta 1196 que lo tomaron los Almohades y fue recuperado el 25 de enero de 1232 definitivamente por las tropas del obispo de Plasencia don Domingo y de las Ordenes Militares.
Juan II de Castilla entrega como dote el Castillo a su yerno el infante aragonés don Enrique, este se hará fuerte después contra el rey castellano y hubo de huir al castillo de Montánchez cuando llegó don Álvaro de Luna al quite aprovechando la retirada para quemar los arrabales de San Martín y San Clemente. Aun así Don Álvaro tendrá que luchar contra Quincoces y convencer a Pedro Alfonso de Orellana que habían quedado como alcaides de la fortaleza por el Infante. Lo consiguió.
En 1446 don Álvaro de Luna, Condestable de Castilla y Maestre de Santiago será nombrado primer duque de Trujillo y señor del Castillo. Es la primera vez que un Maestre de Santiago es amo de Trujillo, por poco tiempo pues a la muerte de Álvaro de Luna Trujillo vuelve a pasar a la Corona.
Don Enrique IV concede la Fortaleza a Álvaro de Zúñiga que llega con el Rey a Trujillo en 1469 para hacerse cargo pero el alcaide del Castillo don Gracián de Sese se niega a ello ante el mismo Rey diciendo que no lo entrega porque "ni cumple a Su servicio ni al bien de Vuestros reinos...".
Al final el Rey cambia la donación del Castillo para don Juan Pacheco marqués de Villena, Maestre de Santiago, que muere en Santa Cruz cuando el alcaide Gracián de Sese está a punto de entregar la fortaleza, a cambio de la villa de Sahelices de los Gallegos, el trueque lo hace con el hijo del maestre difunto don Diego López Pacheco y nuevo marqués de Villena que coloca de alcaide en la fortaleza a su escudero Pedro de Baeza.
A la muerte de Enrique IV el marqués de Villena se hace fuerte en el Castillo contra
Isabel y Fernando apoyando la causa de la Beltraneja que estuvo refugiada en la fortaleza
poco tiempo pues no había seguridad ante la actitud de Luis de Chaves y los Monroy.
Durante más de un año aguantó Baeza el asedio de los aliados isabelinos... Al final se
rindió el 24 de Junio de 1477, a la llegada de la reina Isabel que estaba en Guadalupe y
que vino con la novedad artillera de lombardas...
Se acuerda en 1547 construir la ermita del Castillo dedicada a Santa María de la Victoria como Patrona de la Ciudad, la obra se encargó a Sancho de Cabrera por cien ducados, así lo estableció el Concejo. La imagen tallada en granito que hoy conocemos la realizó Diego Durán en 1531 retocándola Juanes de la Fuente en 1583, la policromó y doró Juan Sánchez.
El 24 de Septiembre de 1566 el rey Felipe II concede al hijo de Hernando y Francisca, Francisco Pizarro nieto del Conquistador, el título de Alférez Mayor de Trujillo; le correspondía llevar el Pendón de la ciudad o cualquier bandera importante siendo quien las custodiaba junto con los atambores. Podía delegar en otra persona para ejercer como Procurador en Cortes y como era menor de edad no ejerció hasta el 14 de Enero de 1572; poco lucida fue su gestión en el cargo amén de sus continuas pendencias y chulerías, le llamó al orden el Concejo por hacer obras anómalas en el castillo abriendo dos ventanas en la cara Sur, hubo de cerrarlas por su cuenta.
En 1591 estuvieron presos en el castillo Gómez Solís y el comendador Luis de Carvajal. El tiempo lo fue arruinando por desuso, en 1596 se hubieron de apañar varias murallas desplomadas gastándose 165 reales... Se reparó igualmente cuando las guerras Carlistas de 1834.
En el 1838 movilizaron a todos los ociosos de la ciudad y comarca para que se ganaran unas perras reparando la fortaleza. A partir del final de estas guerras y al marchar Don Carlos casi V al exilio se acabó de asilvestrar la fortaleza quedando a merced de cualquiera.
Al final el castillo lo vendió el Estado el 25 de Agosto de 1906 a Plácido Beato Pizarro por 4230 pesetas. En 1925 es declarado Monumento Histórico Artístico por lo que el Ayuntamiento decide comprarlo y restituirlo al patrimonio local. La operación se completa el 30 de Agosto de 1929 pagando a Lucía Beato Terso veinte mil doscientas treinta pesetas. Yo conocí el Castillo cuando en él pastaban las ovejas de Nicolás.