وصفاقس، ولعل ذلك ما أوغر عليه صدر تميم، فأوعز إلى أمراء بنى رياح أن يهاجموا الناصر قبل أن يفتك بهم، ونازلهم فى سبيبة شرقى الجزائر ودارت عليه الدوائر، غير أن الناصر استطاع أن يسترد ما كان معه من البلدان فى الاقليم التونسى حتى القيروان. وكان يحدث شغب فى كثير من البلدان ويستطيع الناصر القضاء عليه، وصافته زناتة، وعادت العلاقات حسنة بينه وبين تميم بن المعز. وكان بعيد النظر فعمل على التسامح مع المسيحيين ببلاده حتى يشعروا بالأمان، ويعظم إنتاجهم وعملهم فيها، وأرسل إلى البابا جريجورى السابع بتكريس قسيس يسمى سرفاند أسقفا لأبرشية بونة وافتدى جميع الأسرى المسيحيين فى بلاده أو مملكته. وكان لذلك أثر طيب فى نفس البابا فأجابه إلى تكريس سرفاند ورد عليه سنة 469 هـ/1076 م برسالة لطيفة قال فيها إن المسلمين والمسيحيين جميعا يؤمنون بإله واحد خالد. وخوفا على القلعة عاصمة الدولة من أن يصيبها من التخريب على أيدى العربان من بنى هلال ما أصاب القيروان وغيرها من مدن إفريقية التونسية بنى بجاية على البحر المتوسط فى الشمال سنة 461 هـ لتكون عاصمة جديدة للدولة، وعنى بتخطيطها وتشييد قصور شامخة فيها وظلت بعده تشتهر بما فيها من مساجد ومدارس وفنادق وحمامات ومستشفيات.
وخلفه ابنه المنصور سنة 481 هـ/1088 م وفى أول حكمه ازداد ضغط القبائل الهلالية عليه واضطرته إلى أن تتقاسم معه نصف غلة الأرض، مما جعله يصمم على هجران القلعة إلى مدينة بجاية سنة 473 هـ/1080 م. وخلال السنتين اللتين قضاهما فى القلعة شيّد عددا من القصور، حتى إذا اتخذ بجاية عاصمة له شاد بها طائفة من القصور أهمها قصر اللؤلؤ، وخرج عليه بعض الثوار فى بونة وقسنطينة، وعادتا إليه، واشتبك مع زناتة فى الجنوب الغربى وردّ المرابطين إلى المغرب الأقصى بعد أن استولوا على تلمسان وتقدموا إلى مدينة الجزائر. وظل سيد الجزائر دون منازع إلى وفاته سنة 498 هـ/1104 م. وتولى الدولة بعده ابنه باديس، وكان فظا سريع الغضب، وتوفى بعد ستة أشهر من حكمه، وولى بعده أخوه العزيز، وعمل على عودة السلام بين قبيلته صنهاجة وقبيلة وامانو الزناتية وتزوج بنت زعيمها ماخوخ، وكانت أيامه هادئة وآمنة. وعنى بتشجيع الحركة العلمية والأدبية وإعداد بجاية لإيواء اللاجئين من الأدباء والعلماء الذين غادروا القلعة إلى عاصمته حين تدهورت وأصبحت نهبا للأعراب، وكانوا قد أخذوا يتوغلون من جبال البابور إلى بونة. وتوفى العزيز سنة 518 هـ/1124 م وخلفه ابنه يحيى ولم يستطع إعادة الدولة إلى ما كانت عليه إذ اتسعت زغبة وغيرها من القبائل الهلالية فى التخريب والقضاء على العمران فى الجزائر وخوفا على ما فى القلعة من ذخائر وطرف ومن أدوات ترف وبذخ نقلها يحيى إلى بجاية سنة 543 للهجرة.