Quand les musulmans arrivent à Béjaïa au VIIIe siècle de l'ère chrétienne, elle avait perdu de son importance, puisqu'on ne l'évoque pas. En 1067, le prince hammadite, al-Nas'îr, «le Victorieux», s'est emparé de la montagne y fondant, sur l'emplacement de l'ancienne ville, une nouvelle cité qu'il prend aussitôt pour capitale. Il l'orne de belles mosquées et de magnifiques palais, dont le fameux Qasr al Lu'lu'a, (le Palais de la Perle), il peuple la ville de savants, d'écrivains et d'artistes, faisant d'elle une rivale de Tunis et de Kaïrouan. Al-Nas'îr donne son nom à la nouvelle ville, al-Nas'iriya. Mais ce nom ne va pas effacer l'ancien, Béjaïa, qui, en fait, est l'altération du nom berbère, Bgayet, aujourd'hui encore utilisé. C'est sous le nom de Béjaïa que les cartes maritimes européennes du Moyen-Age, les portulans, la désignaient : Bugia, Buzia, Bugea, Buzana, dont seront tirés les noms bougie et basane, (la peau de mouton tannée), deux produits, notamment la cire, la fameuse candella de Bugia, importés en grande quantité de Béjaïa. Comme ses ancêtres, al-Nas'îr est un grand guerrier, mais aussi un bâtisseur, un civilisateur qui, comme son ancêtre Hammad, fondateur de la Qalaâ des Banu Hammad, va faire de sa ville un pôle de civilisation.
