كان أبوه أفرس فارس باليمن، ومسروق ابن أخت عمرو بن معدي كرب، وعمرو خاله.
وقال مجالد (1) عن الشعبي عن مسروق: لقيت عمر بن الخطاب، فقال: ما اسمك؟ فقلت: مسروق بن الأجدع. قال:
سمعت النبي صلى الله عليه وسلم يقول: " الأجدع شيطان " (2) أنت مسروق بن عبد الرحمان. قال: الشعبي: فرأيته في الديوان (3) مسروق بن عبد الرحمان.
وقال مالك بن مغول (4) سمعت أبا السفر عن مرة قال:
ما ولدت همدانية مثل مسروق.
وقال أيوب الطائي (5) عن الشعبي: ما علمت أن أحدا كان (6) أطلب للعلم في أفق من الآفاق من مسروق.
وقال منصور (7) عن إبراهيم: كان أصحاب عبد الله الذين يقرئون الناس ويعلمونهم السنة: علقمة، والأسود، وعبيدة ومسروق، والحارث بن قيس، وعمرو بن شرحبيل.