وصفاقس، ولعل ذلك ما أوغر عليه صدر تميم، فأوعز إلى أمراء بنى رياح أن يهاجموا الناصر قبل أن يفتك بهم، ونازلهم فى سبيبة شرقى الجزائر ودارت عليه الدوائر، غير أن الناصر استطاع أن يسترد ما كان معه من البلدان فى الاقليم التونسى حتى القيروان. وكان يحدث شغب فى كثير من البلدان ويستطيع الناصر القضاء عليه، وصافته زناتة، وعادت العلاقات حسنة بينه وبين تميم بن المعز. وكان بعيد النظر فعمل على التسامح مع المسيحيين ببلاده حتى يشعروا بالأمان، ويعظم إنتاجهم وعملهم فيها، وأرسل إلى البابا جريجورى السابع بتكريس قسيس يسمى سرفاند أسقفا لأبرشية بونة وافتدى جميع الأسرى المسيحيين فى بلاده أو مملكته. وكان لذلك أثر طيب فى نفس البابا فأجابه إلى تكريس سرفاند ورد عليه سنة ٤٦٩ هـ/١٠٧٦ م برسالة لطيفة قال فيها إن المسلمين والمسيحيين جميعا يؤمنون بإله واحد خالد. وخوفا على القلعة عاصمة الدولة من أن يصيبها من التخريب على أيدى العربان من بنى هلال ما أصاب القيروان وغيرها من مدن إفريقية التونسية بنى بجاية على البحر المتوسط فى الشمال سنة ٤٦١ هـ لتكون عاصمة جديدة للدولة، وعنى بتخطيطها وتشييد قصور شامخة فيها وظلت بعده تشتهر بما فيها من مساجد ومدارس وفنادق وحمامات ومستشفيات.
وخلفه ابنه المنصور سنة ٤٨١ هـ/١٠٨٨ م وفى أول حكمه ازداد ضغط القبائل الهلالية عليه واضطرته إلى أن تتقاسم معه نصف غلة الأرض، مما جعله يصمم على هجران القلعة إلى مدينة بجاية سنة ٤٧٣ هـ/١٠٨٠ م. وخلال السنتين اللتين قضاهما فى القلعة شيّد عددا من القصور، حتى إذا اتخذ بجاية عاصمة له شاد بها طائفة من القصور أهمها قصر اللؤلؤ، وخرج عليه بعض الثوار فى بونة وقسنطينة، وعادتا إليه، واشتبك مع زناتة فى الجنوب الغربى وردّ المرابطين إلى المغرب الأقصى بعد أن استولوا على تلمسان وتقدموا إلى مدينة الجزائر. وظل سيد الجزائر دون منازع إلى وفاته سنة ٤٩٨ هـ/١١٠٤ م. وتولى الدولة بعده ابنه باديس، وكان فظا سريع الغضب، وتوفى بعد ستة أشهر من حكمه، وولى بعده أخوه العزيز، وعمل على عودة السلام بين قبيلته صنهاجة وقبيلة وامانو الزناتية وتزوج بنت زعيمها ماخوخ، وكانت أيامه هادئة وآمنة. وعنى بتشجيع الحركة العلمية والأدبية وإعداد بجاية لإيواء اللاجئين من الأدباء والعلماء الذين غادروا القلعة إلى عاصمته حين تدهورت وأصبحت نهبا للأعراب، وكانوا قد أخذوا يتوغلون من جبال البابور إلى بونة. وتوفى العزيز سنة ٥١٨ هـ/١١٢٤ م وخلفه ابنه يحيى ولم يستطع إعادة الدولة إلى ما كانت عليه إذ اتسعت زغبة وغيرها من القبائل الهلالية فى التخريب والقضاء على العمران فى الجزائر وخوفا على ما فى القلعة من ذخائر وطرف ومن أدوات ترف وبذخ نقلها يحيى إلى بجاية سنة ٥٤٣ للهجرة.