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