El estudio de la necrópolis prerromana de Medellín, que ha proporcionado gran cantidad de material de época tartésica, ha permitido identificarla con Conisturgis, capital de los conios, que fue destruida por los lusitanos.

La Metellinum romana fue fundada por el cónsul Quintus Caecilius Metellus Pius alrededor del 79 a.C. En honor a su fundador recibirá su primera denominación Metellinum. Existen diversos restos de esta época, que demuestran la vitalidad romana de la zona: restos de un puente romano, que más tarde sería sustituido por uno medieval, Villas romanas, o restos del foro aún por excavar en la falda del castillo.

El teatro romano de Medellín se localiza en la ladera sur del Cerro del Castillo, dentro de los límites de un importante yacimiento arqueológico, cuyos orígenes se remontan al Bronce Final y el período Orientalizante.

El grado de romanización del territorio, puesto de manifiesto por la proliferación de las villas romanas en torno a las vegas del río Guadiana, tomando como centro la localidad de Medellín, viene señalado por la dedicación de sus moradores a tareas de tipo rural, preferentemente agrícola con un elevado grado de concentración pese al pujante atractivo que debió de poseer la próspera ciudad de Mérida, situada a escasa distancia. Las relaciones de Medellín con otros núcleos urbanos de época romana se basan en que, desde Mérida, la vía que conducía a Toledo discurría por las inmediaciones de Medellín; a su paso, salvando el Guadiana, salía una bifurcación hasta Córdoba.

En la época visigoda Medellín no perdió su antigua importancia debido a su estratégica localización, siguiendo estando muy influida por su cercanía a la ciudad de Mérida. De este tiempo es la necrópolis hallada en el Turuñuelo.

Los musulmanes llegan a Medellín en el año 768, al mando de Shaqya ben Abd Alwahid. Una vez asentados en Medellín, reconstruyen la fortificación romana que estaba situada en la cima del cerro por considerarla un lugar estratégico en su ocupación del territorio. Del antiguo castillo musulmán sólo se conserva un importante aljibe de dos naves. Cuando Alfonso IX avanza desde Coria sobre Alcántara en 1213, la ocupación árabe recibe ayuda de las plazas de Medellín, Mérida, Badajoz y Cáceres, aunque finalmente la victoria se decanta del lado del rey leonés. Alfonso IX reconquista Medellín por primera vez en el 1227, aunque dos años después vuelve a manos musulmanas, junto con Alange y Guareña. En 1234 Fernando III lo incorpora definitivamente a la Corona de Castilla.