Au début du X ème siècle, en l'an 903, deux chefs andalous obtinrent des peuplades berbères, l'autorisation de bâtir une ville dans les environs de la rade où mouillaient leurs bâteaux.

Avec une troupe de marchands, ils fonèrent une cité sur les pentes du Murdjadjo à proximité d'un petit oued. La vile qui prit le nom de Ouahran (Oued-el-Ouahran : ruisseau sauvage, dur à remonter) puis Oran, ne tarda ghère à devenir très prospère.

Une enceinte de terre durcie s'éleva et de nombreuses familles des environs vinrent s'y installer.

Pisans et Genois faisaient avec Oran un commerce considérable; une commanderie maltaise de l'ordre de Saint Jean de Jérusalem obtint même la faveur d'y fonder un établissement et construisit, à cet effet, trois grosses tours (on voit ces tours encore ajourd'hui sur la partie ouest de Château-Neuf) sur l'escarpement rocheux qui dominait la ville.

Tour à tour omeyade et fatimide, Oran eut à soutenir de nombreux sièges jusu'en 1347 où Abou Hassen Ali, sultan mérinide du Maroc s'e empara.

Se rendant immédiatement compte de l'importance stratégique des tours maltaises, le premier soin du sultan fut de les relierentre elles par des murs très épais, derrière lesquels une petite troupe put facilement tenir en échec de nombreux assiègeants.

Ce fort reçut le nom de Bordj el Ah'meur ("le fort rouge" peut être à cause de la terre rouge dont était fait les murs).

Le Château-Neuf était né.