Hay constancia de habitación en éste término desde época prerromana, tal y como lo demuestra la presencia de varios castellares, como el del Castillo o el de Castilnegro, e incluso de una motilla encontrada en la década de los 70 y ubicada a la salida del pueblo. La división que existían entre los pueblos prerromanos hace pensar que el Guadiana, a su paso por este municipio, pudo hacer de frontera entre Oretanos y Lusitanos, ocupando los primeros la margen izquierda, mientras que los segundos lo harían de la derecha.
Una vía de época romana cruzaba el extremo SE del término, identificada en la Edad Media como el Camino Toledano o de la Barca, que unía Toledo con Mérida. El paso del río Guadiana se hacía a través de una barca, existiendo desde la época de la Reconquista, tal y como lo demuestra la existencia de varios testimonios en diferentes documentos históricos donde aparecen topónimos como el del Camino de la Barca y la Atalaya de la Barca.
Este territorio probablemente dependió de Piedrabuena en época musulmana, pasando a depender del reino de Badajoz, tras la caída de Toledo en 1085, hasta la absorción de éste por los Almorávides en 1099. Con el comienzo de la reconquista en el siglo XII Puebla de Don Rodrigo seguiría dependiendo de Piedrabuena, estando incluida dentro de los límites del Campo de Calatrava en 1189.
Antes de su emergencia como villa independiente era una aldea de Piedrabuena con nombre incierto, tal vez de Casas o Cuevas del Guadiana, de tan escasa importancia que en el mes de mayo de 1472 se fundó sobre ella como puebla, es decir, de nueva creación, adjudicándose el nombre del maestre que el otorgó el privilegio fundacional, Don Rodrigo Tellez Girón.
En 1534 el maestrazgo de la Orden de Calatrava asignó la totalidad de los derechos de este pueblo a la encomienda de Bolaños, pasando en 1563 a la Rinconada de Almodóvar a la que perteneció hasta la desaparición de estas jurisdicciones en el siglo XIX.
También de ésta época es la formalización de los Caminos Reales, uno de los cuales entre Toledo y Sevilla seguía el antiguo camino de La Plata.
En el Capítulo General de 1652 se ordena la agregación del compulso de la Puebla de Don Rodrigo, de treinta vecinos y mil reales, a la de Agudo que lo es de 400 vecinos.
En la división que se hizo de España en forma de Departamentos y Prefecturas durante la dominación francesa, este término estuvo adjudicado al llamado del Guadiana y Guadajira, con capital en la ciudad Mérida, que alcanza hasta el río Bullaque.
En 1826 esta villa contaba con 181 habitantes, parroquia, pósito y un molino en el río Guadiana, existiendo también dos minas, una en el aguadero que hay entre las dehesas del Checa y Las Barcas y otra en el Valle de Santa María.
Al igual que otros pueblos de Los Montes, caracterizados por su aislamiento y agricultura precaria, no empezará a prosperar hasta ya entrada la segunda mitad del siglo XIX, aunque un siglo después, a mitad del XX, la emigración de la población alcanzará al 20% de su población.