البعبع وأمر له بعبيد وخيل وكسا ودنانير. وأوصاه وأرسله وأجاز الرسول الواصل.
وخرجا معا إلى أن وصلا إلى بجاية، وهى حينئذ منزل ينزله رعية البربر. فنظرها ابن البعبع وتأملها، وقال فى نفسه: «هذا المكان يصلح مدينة ومرسى وصناعة للسفن» . وتمادى إلى أن وصل إلى القلعة ودخل على الناصر، وقد علم ابن البعبع أن الوزير محب فى دولة تميم.
فلما انبسط ودفع المكاتبة، قال للناصر: «يا مولاى، معى وصية إليك فأحب أن يخلى المجلس» . فقال الناصر: «ليس هنا إلا الوزير، وأنا لا أخفى عنه أمرا» . فقال: «بهذا أمرنى «١» سيدنا تميم» . فقال الناصر لوزيره: «انصرف» . فلما خرج، قال محمد للناصر: «يا مولاى، إن الوزير مخامر عليك مع تميم، وهو لا يخفى عنه من أمورك شيئا، وتميم مشغول مع عبيده النصارى.
قد «٢» استبد بهم واطرح صنهاجة وتلكاتة وجميع القبائل. فو الله، لو وصلت بعسكر إلى المهدية ما بتّ إلا فيها لبغض الأجناد والرعية فى تميم، وأنا أشير عليك بما تملك به المهدية وغيرها. وقد عبرت الآن ببجاية فرأيت فيها مرافق من صناعة وميناء وجميع ما يصلح لبناء مدينة. فاجعلها لك مدينة، يكون فيها دار ملكك وتقرب من جميع بلاد إفريقية. وأنا أنتقل إليك بأهلى وولدى، وأترك مالى بالمهدية من الرياع، وأخدمك حق الخدمة» . فأجابه الناصر إلى ذلك واستراب من وزيره.