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