La ville aurait été fondée au début du Xe siècle de l'ère chrétienne, en 903, ou, selon une autre estimation, en 937. Des marins andalous, voulant assurer un relais pour leur commerce avec Tlemcen et d'autres régions de l'intérieur, auraient édifié les premières constructions : des entrepôts et quelques habitations, ce qui suppose une présence permanente. Cet établissement a connu une expansion rapide au point de devenir une ville et d'attiser les convoitises. En 901, la ville est occupée par les Fatimides, dynastie chiite établie au Maghreb à l'époque. Les Almoravides s'en emparent en 1083, puis c'est au tour de leurs successeurs, les Almohades, de l'occuper. Au siècle suivant, c'est au tour d'une autre dynastie berbère, les Mérinides, de la conquérir : les Mérinides, qui avaient occupé tout le Maroc et une partie de l'Andalousie, ambitionnaient de s'emparer de tout le Maghreb, mais ils se sont arrêtés à Oran. Ces changements successifs de dynasties n'ont pas empêché Oran de prendre de l'importance : la ville commerçant non seulement avec les autres contrées du Maghreb et de l'Andalousie, mais elle avait aussi des relations commerciales avec les villes de Marseille, Gênes et surtout Venise, auxquelles elle vendait de la laine, des tapis, des burnous, des noix, du cumin et d'autres produits recherchés à l'époque.
