وأمه من بني مالك بن عَمرو بن تميم وهو الرومي قيل له ذلك لأن الروم سبوه صغيرا.
قال ابن سعد، وكان أبوه وعمه على الأبلة من جهة كسرى وكانت منازلهم على دجلة من جهة الموصل فنشأ صهيب بالروم فصار ألكن ثم اشتراه رجل من كلب فباعه بمكة فاشتراه عَبد الله بن جدعان التميمي فأعتقه، ويُقال: بل هرب من الروم فقدم مكة فحالف ابن جدعان.
وروى ابن سَعْد أنه أسلم هو وعمار ورسول الله صَلى الله عَلَيه وسَلم في دار الأرقم.