Una de las épocas más fascinantes es la Edad Media. Existen muy pocos datos históricos sobre la misma y numerosa duda sobres las leyendas y tradiciones orales que hablan sobre la Conquista del Castillo, el Huerto de la Cava o la fundación de Torrejón el Rubio. Podemos diferenciar en una primera época de la conquista árabe de la zona por Musaibn Nusair , en el 713. A partir de ahí poco se conoce, nada más que la construcción del actual castillo de Monfragüe en el 811. La segunda, más fascinante y documentada, es la reconquista de la zona y el azaharoso siglo XII, con continúas guerras, cambios de manos del castillo, la llegada de la Virgen del Monfragüe o la reconquista definitiva y fundación de Torrejón el Rubio.
El escaso poblamiento de la zona en época romana nos hace intuir que la conquista de nuestro término municipal se daría a la vez que la de toda la región. La principal batalla en la región se produce en Mérida, donde Musa Ibn Nusair destituye a Tarik ibn Ziyad, y trae a 18.000 € desde la propia península arábiga para acabar con la dura resistencia emeritense. La batalla dura más de un año, hasta el 13 de junio del 713. Tras las conquistas de Talavera y Toledo, Musa atacará hacia la zona salmantina, eso sí, antes se hará con nuestra comarca. Son días antes de la última gran batalla de la conquista musulmana celebrada a finales de verano del 713 en Segoyuelo de los Cornejos, donde la leyenda sitúa la muerte de D. Rodrigo.
Desde entonces, los árabes, centrados en la conquista de la península ibérica a penas dejan vestigios de su presencia. A partir del siglo IX comienzan el asentamiento y la construcción de diversas fortalezas con el fin de controlar los puntos estratégicos más importantes. Para ello construyen el Castillo de Monfragüe en el 811. Los motivos son evidentes, dado que desde aquel punto, junto a la red de castillos existente en la zona, tejían un punto estupendo de vigilancia y parapeto ante posibles ataques cristianos.
De toda la época árabe del Castillo existe un gran silencio sobre los acontecimientos. La reactivación de acontecimientos históricos comienza a finales del siglo XI, donde diversas leyendas, sitúan diferentes escaramuzas en la zona entre árabes y cristianos. Buena prueba de la más que lógica existencia de diversas batallas, es el intento de Conquista de Badajoz por parte de Alfonso VI, que sufre una gran derrota en la Batalla de Sagrajas (cerca de Badajoz), el 23 de octubre de 1086. La llegada de los almorávides supuso un duro revés para la reconquista cristiana. El Castillo de Monfragüe vivirá sus momentos más intensos en la segunda mitad del siglo XII. En un momento de gran convulsión entre los reinos de León, Castilla y Portugal, con frecuentes escaramuzas entre los leones y los portugueses, el primer cristiano que reconquistará la zona será Geraldo Geraldes, más conocido como Geraldo Sempavor, que tomará el Castillo, con sus audaces tácticas, en 1166, según las crónicas cristianas.
En 1169 se produce la batalla de Badajoz, donde Geraldo Sempavor y el Rey portugués Alfonso Enriques fueron capturados por Fernando II de León. A cambio de la liberación de ambos, Geraldo Sempavor tuvo que ceder a Fernando Rodríguez de Castro “El Castellano” todas las posesiones que tenían en la zona de acción leonesa y castellano.
Fernando Rodríguez de Castro crea con esas posesiones, incluidas Monfragüe, en un señorío “pseudoindependiente”. La confusión sobre la historia de la fortaleza se genera al conceder el Rey Fernando II el control del Castillo a la Orden de Santiago, aunque aparecen ligados a la familia Fernández de Castro. El rey Alfonso VIII de castilla recupera del Reino de León el Castillo de Monfragüe en 1185, tras esperar 4 años el cumplimiento del Acuerdo del Tratado de Medina de Rioseca. En 1186 aparece por primera vez en las crónicas la aldea de Monfragüe, situada junto al Castillo del mismo nombre.
No obstante, en la última gran oleada almohade el castillo está durante al menos dos años en manos de los musulmanes y no es hasta 1197 cuando es definitivamente conquistado, probablemente por los caballeros de Monfragüe, a los que se les encomienda la protección del enclave a principios de 1196.
Con la reconquista de definitiva de Trujillo en 1232. Comienza la repoblación de la zona. La tipología de repoblación se realiza con abulenses dedicados a la ganadería. Aunque la Aldea de Monfragüe ya existe y sería el claro antecedente de la actual población torrejoniega.
La creación del actual poblamiento no tiene ni origen ni datación clara, salvo que no existen pruebas documentales hasta 1298. La única versión que existe no es más que una leyenda. Según la misma Pedro Rubio, ganadero castellano, se asentó con su familia junto a un Torreón árabe situado en el actual Huerto de a Cava. La toponimia de la localidad vendría, pues, de Torreón y del apellido del primer poblador cristiano tras la reconquista.
Desde esa supuesta creación hasta 1298 Torrejón dependería de la ciudad de Plasencia y en ese momento se hablan de que las propiedades pertenecientes a la aldea de Torrejón el Rubio son de Alfón Durán, alcalde de Plasencia en esa época.