من موضع إلى موضع، وهمه الأندلس، لما كان في نفسه من أمرها ومن الأثر المروي عنه فيها. فوصل إلى مصر؛ ثم سار منها إلى برقة؛ فبقى فيها مستترا مدة. ثم رحل عنها؛ فأوغل في المغرب. قال بدر مولاه: (فأدركته في الطريق، وجهتني إليه أم الأصبغ أخته شقيقته بدنانير وشئ من الجوهر يستعين بها على النفقة والوصول؛ فوصل إلى إفريقية، وصاحبها عبد الرحمن بن حبيب، ومعه يهودي قد خدم مسلمة بن عبد الملك؛ وسمعه يحدث بخبر القرشي الذي يكون من بني أمية يتغلب على الأندلس، اسمه عبد الرحمن، ذو ضفيرتين؛ فنظر إلى عبد الرحمن؛ فوجده بضفرتين؛ فقال لليهودي: (ويحك!) هذا هو المذكور، وأنا قاتله!) فقال له اليهودي: (إن يك ذلك، لم تقتله!) ثم صار ابن حبيب يقتل الواصلين إليه من بني أمية، ويأخذ أموالهم. فهرب عبد الرحمن عن القيروان، ونجا يريد الأندلس، ويشغل نفسه بها لما كان عنده من الروايات في علم الحدثان من قبل مسلمة بن عبد الملك أخي جده وغيره. فسار حتى أتى تادلا من قبائل المغرب؛ فناله عندهم تضييق وأخبار يطول ذكرها. ثم هرب من عندهم حتى أتى نفزة، وهم أخواله؛ فإن أمه كانت من سبيهم. قال بدر: (فجزت إلى الأندلس، واجتمعت بعبيد اله بن عثمان بساحل البيرة، في آخر سنة ١٣٦؛ ثم انصرفت في سنة سبع بعدها، وأقمت عنده مدة؛ ثم كررت منصرفا إلى الأندلس في موالي عبد الرحمن.
حدَّث عبد الرحمن، قال: (دخلت الأندلس، وأنا أضبط جلية مسلمة ابن عبد الملك؛ فإنه أتى جدي هشاما يوما؛ فوجدني عنده صبيا؛ فأمر جدي بتنحيتي عنه؛ فقال له مسلمة: (دعه يا أمير المؤمنين! فإنه صاحب بني أمية ومحيي دولتهم بعد زوالها!) فلم أزل أعرف لي مزية من جدي بعد.)
قال الرازي: وفي سنة ١٣٧، ثار الحبحاب بن رواحة بجهة سرقسطة؛