Le nom actuel de la ville est celui d'une tribu berbère, originaire du Rif. Au XIVe siècle, les Béthioua étaient au service du souverain mérinide ‘Abd el ‘Aziz, en guerre contre le Hafçide Abû Farès. Mis en échec par les armées hafçides à Mazouna et redoutant de rentrer au Maroc, ils se sont installés près de Mostaganem (1370). C'est ainsi que, changeant d'alliance, ils feront, tour à tour, allégeance aux Hafçides, aux souverains de Tlemcen, puis, à partir du XVIe siècle, aux Turcs. C'est en 1784 qu'ils se sont installés près des ruines romaines de Portus Magnus : par un écrit officiel, paraphé par le bey d'Oran, Mohammed El-K'bir, ils échangeaient leur territoire contre celui de la tribu qui campait alors à Bordj. Après la conquête française, les Béthiouis seront déplacés vers l'est, dans les ruines romaines, pour permettre aux colons européens d'occuper leur territoire, jugé plus fertile et plus salubre que les autres sites. C'est sur ce site que les colons construiront le village de Saint-Leu, un saint du calendrier chrétien. Les colons puiseront abondamment dans les pierres des ruines romaines pour construire leurs maisons, puis les édifices publics. A l'indépendance, le nom de Béthioua est donné à l'agglomération, devenue entre-temps une ville.
