توجه عبد الرحمن بن مهدي إلى طلب علم الحديث وهو ابن بضع عشرة سنة، وكان مبرزًا فيه منذ صغره، وكان أول طلبه سنة: نيِّفٍ وخمسين ومائة.
قال أبو عامر العقدي:"كنت سببًا في طلب عبد الرحمن بن مهدي للحديث، فقد كان يتبع القُصَّاص، فقلت له: لا يحصل في يدك من هؤلاء شيء".
أي: لن يفيدك القُصَّاص؛ لأنه لا هم لهم إلا تحديث الناس بما هب ودب من غير تأكد ولا تثبت، والمهم عندهم أن يُغْرِبوا على العامة، ويأتون لهم بالطرف، وأن تشدَّ إليهم الأبصار، وتُفتح لهم الأسماع ولو أتوا بالأعاجيب، فكان يعجبه شأنهم منذ الصغر، ولكن لما نصحه أبو عامر رحمه الله، وقال له: لا يحصل في يدك من هؤلاء شيء، التفت إلى الحديث، وتمييز صحيحه من سقيمه، وطلبه على أصوله، فصار علمًا مبرزًا.
وسمع عبد الرحمن بن مهدي من سفيان الثوري، وهو من أجِلَّة شيوخه، سمع منه سنة: (152هـ) ، و (153هـ) ، و (154هـ) ، و (155هـ) ، و (156هـ) .