Cuatro años anduvo errante Abd al-Rahman, siendo recibido en algunos lugares con indiferencia y en otros con franca hostilidad. Su vida fue bastante misera y aunque una vieja profecía le había augurado un trono, ya empezaba a desconfiar que dicha predicción se cumpliera. Sin embargo, aquellas aventuras y viajes por el norte de África le acabaron llevando a la tribu de los Nafta, de la que era oriunda su madre.

El 14 de Agosto de 755 el príncipe Abd al-Rahman pondría pié en su futuro reino.