En Trujillo no todo es gótico y renacentista, sino también mudéjar. La influencia árabe –omnipresente en gran parte de España– dejó huellas muy claras que, a su vez, se imprimieron sobre lo que quedó de los romanos, quienes fueron los verdaderos fundadores de la original Turgalium. El principal rastro que el mundo musulmán dejó en Trujillo es el castillo situado en los altos de la ciudad, con una tipología típica de las alcazabas del califato de Córdoba (siglo X). En el 1500 el castillo sufrió algunas modificaciones, pero al menos su estructura básica sigue siendo la misma que trazaron los guerreros del Islam.
Fue con la conquista musulmana de España que Trujillo se consolidó como un núcleo de cierta relevancia económica. Durante el siglo IX la zona estaba dominada por la tribu bereber de los Nafza, que sufría las incursiones de los reinos cristianos de la región. Durante los tres siglos siguientes esta ciudad del imperio musulmán se llamó Torgiela. Y de aquella época quedan también los restos muy bien conservados de una muralla con diecisiete torres almenadas rectangulares. De las siete puertas originales de la ciudad amurallada sólo quedan cuatro. La más famosa es la Puerta del Triunfo, por donde pasaron las tropas cristianas el 25 de enero de 1232, cuando la ciudad fue definitivamente recuperadapor la corona de Castilla.