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