En el siglo V de nuestra era los bárbaros hacen caer bajo su espada al decadente Imperio Romano de Occidente. Con parte de la provincia Cartaginense se formó la Oróspeda, quedando comprendida en ésta Ello, denominada en aquel entonces Elo, y toda su jurisdicción militar y eclesiástica. Justiniano, Emperador de Oriente, por tratados con Atanagildo a quien prestó ayuda contra Agila, recibió casi toda la Bética, y la Oróspeda.
Leovigildo declaró la guerra a los griegos-bizantinos y los expulsó de España, ejerciendo dominio sobre toda la península ibérica y formando un reino independiente. Los habitantes de Oróspeda se sublevaron, siendo definitivamente sometidos por Leovigildo. En el año 579 dividió a España en 8 ducados, subdivididos en 75 condados. Con la Oróspeda se formó el ducado de la Aurariola, uno de cuyos siete condados fue Elo que, por corruptela, llamábase entonces Eio.
Ante la invasión musulmana, el Duque de la Aurariola, Teodomiro, presentó batalla en numerosos encuentros. Al morir el Rey don Rodrigo y dispersos los godos, Teodomiro reúne a sus tropas y, obligado por los invasores, se repliega en su ducado, donde tiene lugar una batalla que pierde. Cercado en la capital ducal, el general árabe Abd-ul-Aziz concierta un pacto con el duque por el cual éste se obliga a capitular, pero es reconocido como soberano tributario de su antiguo ducado. Queda así constituido, el 5 de abril de 713, el Reino de Teodomiro, Todmir para los árabes, en el que permanece incluido Eio (Montealegre).
Murió Teodomiro en 743, sucediéndole Atanaildo que se esforzó por mantener la independencia, terminada con la llegada de Abderramán I que puso fin a la capitulación de Abd-ul-Aziz y Teodomiro. Repetidas veces se sublevaron sus habitantes, sin éxito. En el 860 la antigua Aurariola fue invadida pasajeramente por piratas normandos. En el 900 sufrió un terrible terremoto. En el 901 se sublevaron nuevamente sus habitantes intentando recuperar la independencia. Por todas esta vicisitudes paso Eio, denominándose sucesivamente Eloe, Elle y por fin, Eliph, nombre con que fue conocida por los árabes.