ولا اعرف لمالك شيئا يتمسك به في أنه صحابي الا حديثين اختلف بعض الرواة فيهما هل هما لعبد الله أو لمالك ولا ترجم البُخارِيّ ولا بن أبي حاتم ولا من تبعهما لمالك في الصحابة حتى ان بن حاتم رتب آباء من اسمه مالك على الحروف فلما ترجم حرف الباء الموحدة بيض ولم يذكر أحدا.
وأول من ترجم لماك ابن بُحَيْنَة ابن شاهين فقال مالك ابن بُحَيْنَة ولم يزد على ذلك ولم يورد له شيئا فتبعه ابن عَبد البَرِّ كعادته وزاد عليه ما رأيت وها انا اذكر شبهة من ذكره في الصحابة قال ابن مَنْدَه: مالك ابن بُحَيْنَة روى حديثه سعد بن إبراهيم، عَن حفص بن عاصم، عَن مالك ابن بُحَيْنَة والصواب عَبد الله بن مالك ابن بُحَيْنَة.
وأخرج البُخارِيّ من طريق بهز بن أسد، عَن شعبة، عَن سعد بن إبراهيم، عَن حفص بن عاصم، عَن مالكٍ ابن بحينة أَنَّ النَّبِيَّ صَلى الله عَلَيه وسَلم رأى رجلا يصلي ركعتين وقد أقيمت الصلاة فقال اتصلي الصبح أربعا وقال بعده تابعه غندر ومعاذ، عَن شعبة.
وقال ابن إسحاق، عَن سعد بن إبراهيم، عَن حفص، عَن عَبد الله وقال حماد، عَن سعد، عَن حفص، عَن مالك.