Por el lado de levante está la Albacara, que prolonga el conjunto macizo del castillo en forma de planta de hexágono irregular, por las características constructivas este espacio se adosó veinte años después al Patrio de Armas. En su interior se encuentra una pequeña ermita del siglo XVI dedicada a San Pablo para conmemorar el día que se reconquistó Trujillo, el 25 de enero de 1232, día de la conversión del santo. Junto a la ermita hay un pozo con brocal de piedra, para suministrar agua a los animales. La palabra "albacara" (del ár. Al-baqqara, la vaquería) define a un recinto murado en la parte exterior de una fortaleza, con entrada en la plaza y salida al campo, y en el cual se solía guardar ganado vacuno. Este edificio castrense se utilizó para albergue de la guarnición y se dedicó a los distintos servicios de mantenimiento de la tropa y almacén, por eso no existen dependencias, pues se realizarían con materiales más perecederos que la piedra. La Albacara está rodeada, en parte, por una barbacana de época cristiana.

Realmente las fuentes árabes existentes sobre Trujillo son pocas y parcas. Sabemos que en el 881 hay una incursión de Alfonso III contra los Nafza, que ocupaban la zona, que en el 317 Héjira/929-30 d. C. se nombra gobernador militar de Trujillo a Ahmad Ibn Sakan. Ibn Jaldun la cita al igual que Al Idrisi y al Himyari y entre las crónicas cristianas que lo citan está la Primera Crónica General de Alfonso el Sabio y los Anales Toledanos II, que citan su Reconquista en 1232. Estos datos históricos avalan una fecha de construcción del castillo en la segunda mitad del siglo IX, posterior al modelo emeritense. Las torres albarranas son contemporáneas al resto de las obras, ya que estuvieron unidas con los cubos del castillo mediante arcos de los cuales quedan hoy restos del lugar de sus engarjes que se corresponden de lado a lado, y que son exactos a los exisntentes en la Alcazaba de Mérida, no solo en obra sino también en similitud de dimensiones y de aparejo.

El castillo de Trujillo en tiempos de Pedro I fue elegido para que el tesorero del rey, el judío Samuel Leví, guardase las riquezas de la Corona, porque se la consideraba una de las fortalezas más seguras del reino.

Aquí se refugió Juana "la Beltraneja" en su disputa con la reina Isabel I en una época de agitación familiar y social. Una vez entregado el castillo a la reina Católica, Juana tuvo que salir huyendo hacia Plasencia, donde se casó con Alfonso V de Portugal.

Este recinto fortificado es muy visitado diariamente, aquí se venera la imagen de Ntra. Sra. de la Victoria, Patrona de la Ciudad. El concejo acordó desde 1531 que la imagen que en dicho año ejecutara el cantero Diego Durán, se colocase entre las dos torres del castillo, cumpliendo así con la venerable leyenda según la cual la Virgen se apareció con el Niño en sus brazos entre dos torres de la muralla, gracias a ella se reconquistó la ciudadela. Así se representa en el escudo de la Ciudad. En la ermita de la Virgen, la Hermandad de la Virgen de la Victoria con motivo de la celebración de sus Bodas de Oro, colocó un mosaico de azulejos relatando este acontecimiento histórico tan importante para Trujillo .