وذلك بعد أن عرض الأمر على سليمان بن كثير وعلى قحطبة فرفضـا1 ليمثله فـــــــي خراسان. وكتب معه إلى شيعته كتاباً قال فيه: "بسم الله الرحمن الرحيم صدق وعد الله لأوليائه، وحقت كلمة الله على أعدائه، ولا تبديل لكلمات الله، ولن يخلف الله الميعاد، أن تستفتحوا فقد جاءكم الفتح، فقطع دابر القوم الذين ظلموا والحمد لله رب العالمين… أما بعد فقد وجهت إليكم مجد الدهر عبد الرحمن بن مسلم مولاي، فالقوا اليه أزمة أموركم، وحملوه أعباء الوزر لها والصدر في محاربة عدوكــم، وعاهدوا الله على الطاعة وكونوا بحبله معتصمين. ﴿وَعَدَ ٱللَّهُ ٱلَّذِينَ ءَامَنُواْ مِنكُمْ وَعَمِلُواْ ٱلصَّٰلِحَٰتِ لَيَسْتَخْلِفَنَّهُمْ فِى ٱلْأَرْضِ كَمَا ٱسْتَخْلَفَ ٱلَّذِينَ مِن قَبْلِهِمْ وَلَيُمَكِّنَنَّ لَهُمْ دِينَهُمُ ٱلَّذِى ٱرْتَضَىٰ لَهُمْ وَلَيُبَدِّلَنَّهُم مِّنۢ بَعْدِ خَوْفِهِمْ أَمْنًا ۚ يَعْبُدُونَنِى لَا يُشْرِكُونَ بِى شَيْـًٔا ۚ وَمَن كَفَرَ بَعْدَ ذَٰلِكَ فَأُوْلَٰٓئِكَ هُمُ ٱلْفَٰسِقُونَ﴾"2.
وكان تعرّف أبي مسلم للمرة الأولى على الدعوة العباسية حينما التقى ببعض النقباء العباسيين الذين زاروا بعض العجليين في سجن الكوفة وهم في طريقهم إلى أداء فريضة الحج، وكان أبو مسلم يخدم هؤلاء العجليين (من بني معقل) فـي السجن، فتوسموا فيه نجابة وعقل وأدب فضموه إلى دعوتهم واصطحبوه معهم إلى إبراهيم الإمام بعد أن استأذن مولاه عيسى بن إبراهيم السراج3 وأعجب الإمام أخلاقه ومنطقه ورأيه وعقله4 وغيّر اسمه إلى عبد الرحمن وكناه بأبي مسلم وظـل فــي خدمته يستعمله في حمل رسائله إلى الكوفة وخراسان حتى سنة ۱۲٨هـ حین أشخصـه إلی خراسان.
وكان أبو مسلم على معرفة بأحوال خراسان ـ التي كانت الفتنة قد طالت فيهـا بین نصر بن سيار وعلي بن الكرماني ومن كان بها من العرب حتى أضجر ذلك كثيـــــراً من أصحابهما وجعلت نفوسهم تطلع إلى غير ما هم فيه وإلى أمر يجمعهم فتحركت
