En arrivant au pouvoir en 1062 (453 de l'hégire), al Nas'ir va continuer l'œuvre de ses ancêtres. Il renforce la puissance de la Qal'a et cherche à l'agrandir. C'est ainsi qu'il jette son dévolu sur la région de Béjaïa dont il s'empare. Si Béjaïa a connu des heures de gloire durant la période romaine (elle s'appelait alors Saldae), elle est tombée depuis longtemps dans le déclin et s'est transformée en bourgade sans grande importance, en tout cas, les historiens musulmans ne l'évoquaient pas. Al Nas'ir, fils d'Alennas, quatrième souverain de la dynastie hammadite, va lui redonner un second souffle. Il démolit les vieux bâtiments et en construit de nouveaux, plus solides et surtout plus beaux. Le prince a pris soin, en quittant la Qala'a, de s'installer dans sa nouvelle capitale, en emmenant avec lui architectes, géomètres, maçons et décorateurs choisis parmi les meilleurs artisans. Et pour sa résidence, il va faire construire un palais au milieu de la ville. Ses architectes et ses décorateurs vont se surpasser à un point tel que lorsqu'il sera achevé, ce palais paraîtra comme une perle dans un écrin. C'est pour cela qu'on l'appellera Qasr al Lu'lu'a, (le Palais de la Perle), et sa beauté sera longtemps chantée par les poètes et les amoureux des belles choses.
