Médéa est passée par plusieurs appellations suivant les civilisations qui se sont succédées dans la région. Certains avancent que Médéa vient de Lemdouna, nom d'une tribu berbère (Sanhadja) et celui qui en fait partie est appelé El medi ou El medani, en référence à la fabrication des couteaux appelé el mada qui était le métier des habitants de la région.

​

D'autres disent que c'est un nom d'origine romaine : Lembdia. Il serait le nom d'une reine romaine qui a régné sur la ville au début de l'ère chrétienne. Elle a même pris le nom de Medias ou Amdekes car elle se trouvait à mi-chemin entre deux villes romaines : Thamaramusa (Berrouaghia) et Sufsar (Amoura).

Quoiqu'il en soit, Médéa, avant la dénomination romaine, faisait partie du royaume de Numidie sous le commandement des berbères, à leur tête Takfarinas, et étaient farouchement hostiles à la présence romaine. Ce dernier a conduit de grandes révoltes contre les romains, notamment dans la région de Berrouaghia ; ce qui n'évitera pas à Médéa de tomber sous l'emprise romaine à la fin du 1er siècle de l'ère chrétienne et pris le nom de Admedias sous le règne de Sibtem Sfar.

​

Conformément à la politique militaire romaine, Médéa, comme la plupart des régions conquises par Rome, devint tout d'abord un important centre militaire et a servi de lieu de résidence à la communauté romaine. Elle deviendra vite une ville romaine à l'instar de toutes les autres cités de la Maurétanie césarienne.

​

Dans ses envions immédiats, plusieurs villes furent édifiées comme Auzia (Sour El Ghozlane) que Septémus Souasius a érigé en colonie pour faciliter l'accès vers le sud et l'ouest.

​

Certaines villes érigées aux alentours de Médéa constituaient pour la plupart des postes de surveillance ou des remparts pour cette ville qui avait été entourée d'une imposante muraille défensive afin de la prémunir de tout danger extérieur et des attaques des Guitols sahraouis aux frontières de l'empire romain. Cependant, la présence romaine à Médéa ainsi que dans toute l'Afrique du Nord fut compromise par l'invasion vandale sous le commandement de Genséric en 409 après J.C.

​

Les romains furent chassés de la ville qui retrouvera un semblant d'indépendance grâce à ses nouveaux dirigeants berbères tel que Boukmina qui soutenaient Genséric tant pour se prémunir contre sa tyrannie que pour maintenir leurs intérêts. Mais cette alliance ne durera pas longtemps à cause de la révolte des berbères menés par Antalas. Il en fut ainsi jusqu'à l'arrivée des byzantins à la fin du 4ème siècle après J.C. Ces derniers prendront le pouvoir et occuperont la ville jusqu'en l'an 650 après J.C., date à laquelle la conquête musulmane commença au Maghreb.