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

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

وفى مساء هذا الانتصار فى اليوم العاشر من ذى الحجة سنة 138 للهجرة دخل عبد الرحمن القصر بقرطبة وصلّى بالناس وخطب فى الجند معلنا ميلاد الدولة الأموية فى الأندلس، وأخذ يحاول جادّا أن تكون دولته فى قرطبة امتدادا لدولة آبائه فى دمشق، وكان أول ما مهّد به لذلك قطعه الخطبة للعباسيين بعد عشرة أشهر من استيلائه فى الأندلس على صولجان الحكم، وحاول بعض دعاة العباسيين أن يثوروا به فى أول أمره، فقبض عليهم وحزّ رءوسهم، وقيل إنه وضعها فى جواليق (أوعية) وعلى رأس كل منهم بطاقة تحمل اسمه وأرسلها إلى والى العباسيين فى القيروان، وقيل: بل أرسلها إلى المنصور، فقال: الحمد لله الذى جعل بينى وبين عبد الرحمن صقر قريش بحرا. وأخذ عبد الرحمن يعمل على تثبيت الحكم بالأندلس فى بيته وأن يكون وراثيّا فى أبنائه وأحفاده، وبذلك حمى