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