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