يجده، وطلب العُدَد فلم يجدها، فلم يزل السعد يخدمه إلى أن سار بنفسه لابن حفصون، فوجده مجتازًا لوادي التفاح، ومع أكثر من عشرين ألف فارس -كذا نقل: اليسع، وما أحسب أن ابن حفصون بقي إلى هذا التاريخ- قال: فهزمه، وأفلت ابن حفصون في نفر يسير، فتحصن بحصن مُبشّر.
ولم يزل عبد الرحمن يغزو حتى أقام العوج، ومهد البلاد، ووضع العدل، وكثر الأمن، ثم بعث جيشًا إلى المغرب، فغزا برغواطة بناحية سلا، ولم تزل كلمته نافذة، وسجلماسة، وجميع بلاد القبلة، وقتل ابن حفصون. وصارت الأندلس أقوى ما كانت وأحسنها حالا، وصفا وجهه للروم، وشن الغارات على العدو، وغزا بنفسه بلاد الروم اثنتي عشرة غزوة، ودوخهم، ووضع عليهم الخراج، ودانت له ملوكها، فكان فيما شرط عليهم اثنا عشر ألف رجل يصنعون في بناء الزهراء التي أقامها لسكناه على فرسخ من قرطبة.
وساق إليها أنهارًا، ونقب لها الجبل، وأنشأها مدورة، وعدة أبراجها ثلاثمائة برج، وشرفاتها من حجر واحد، وقسمها أثلاثًا: فالثلث المسند إلى الجبل: قصوره، والثلث الثاني: دور المماليك والخدم، وكانوا اثني عشر ألفًا بمناطق الذهب، يركبون لركوبه، والثلث الثالث: بساتين تحت القصور. وعمل مجلسًا مشرفًا على البساتين، صفح عمده بالذهب، ورصعه بالياقوت والزمرد، واللؤلؤ، وفرشه بمنقوش الرخام، وصنع قدامه بحرة مستديرة ملأها زئبقًا، فكانت النور ينعكس منه إلى المجلس، فدخل عليه قاضيه منذر بن سعيد البلوطي، فوقف، وقرأ: ﴿وَلَوْلَا أَنْ يَكُونَ النَّاسُ أُمَّةً وَاحِدَةً لَجَعَلْنَا لِمَنْ يَكْفُرُ بِالرَّحْمَنِ لِبُيُوتِهِمْ سُقُفًا مِنْ فَضَّةٍ﴾ [الزخرف: ٣٣، ٣٤] الآيتين، فقال: وعظت أبا الحكم. ثم قام عن المجلس، وأمر بنزع الذهب والجواهر.
وقال عبد الواحد المراكشي في "تاريخه": اتسعت مملكة الناصر، وحكم على أقطار الأندلس، وملك طنجة وسبتة وغيرهما من بلاد العدوة، وكانت أيامه كلها حروبًا. وعاش المسلمون في آثاره الحميدة آمنين برهة.
ويقال: إن بناء الزهراء أكمل في اثنتي عشرة سنة، بألف بناء في اليوم، مع البنّاء اثنا عشر فاعلا.
حكى أبو الحسن الصفار: أن يوسف بن تاشفين ملك المغرب لما دخل الزهراء، وقد خربت بالنيران والهدم، من تسعين سنة قبل دخوله إليها، وقد نقل أكثر ما فيها إلى قرطبة وإشبيلية، ونظر آثارًا تشهد على محاسنها، فقال: الذي بنى هذه كان سفيهًا. فقال أبو مروان بن سراج: كيف يكون سفيهًا وإحدى كرائمه أخرجت مالا في فداء أسارى في أيامه، فلم يوجد ببلاد الأندلس أسير يفدى.
توفي الناصر في رمضان، سنة خمسين وثلاث مائة. وستعاد ترجمته مختصرة بزيادات مهمة، وأنه افتتح سبعين حصنًا ﵀.