واختلف في زمن إسلامه ، فقال الحافظ جمال الدين المزي في تهذيب الكمال : ( أسلم في خلافة أبي بكر الصدّيق ، ويقال : في خلافة عمر بن الخطاب ) ، وذكر الحافظ الذهبي في سير أعلام النبلاء : أنه قدم المدينة من اليمن في أيام عمر - رضي الله عنه - فجالس أصحاب محمد - صلى الله عليه وسلم - ، فكان يحدّثهم عن الكتب الإسرائيلية ، وعجائبها ، ويأخذ السنن عن الصحابة ، ورجَّح الحافظ ابن حجر في الإصابة أنَّ إسلامه كان في خلافة عمر .

حدّث عن عمر ، وصهيب ، وغير واحد ، وحدّث عنه من الصحابة : أبو هريرة ، ومعاوية ، وأنس بن مالك ، وعبد الله بن عباس ، وعبد الله بن عمر ، وعبد الله بن عمرو، وعبد الله بن الزبير ، وخريم بن فاتك ، ومعاذ بن أنس ، وهذا من قبيل رواية الصحابي عن التابعي ، والذي وصفه الذهبي بأنه نادر عزيز .

وسأل العباس بن عبد المطلب كعباً : ما منعك أن تُسلم على عهد النبي - صلى الله عليه وسلم - ، وأبي بكر حتى أسلمت الآن على عهد عمر ؟ فقال كعب : إنَّ أبي كتب لي كتاباً من التوراة ودفعه إليَّ ، وقال : اعمل بهذا ، وختم على سائر كتبه ، وأخذ عليَّ بحق الوالد على ولده أَلاَّ أفض الخاتم ، فلما كان الآن ورأيت الإسلام يظهر ولم أر بأساً ، قالت لي نفسي : لعل أباك غَيَّبَ عنك علماً كتمك فلو قرأته . ففضضت الخاتم ، فقرأته ، فوجدت فيه صفة محمد - صلى الله عليه وسلم - وأمته ، فجئت الآن مسلماً .

وسمي بـ ( كعب الأحبار ) ، أو ( كعب الحبر ) لكثرة علمه .

وفي تاريخ دمشق أنَّ ابن سيرين كره أن يقول ( كعب الأحبار ) ولكن ( كعب المسلم ) ، وذلك باعتبار أنَّ لفظة ( الأحبار ) وصف ينصرف إلى علماء اليهود ، كـ ( الرهبان ) وصف ينصرف لعلماء النصارى ، فلذا كره ذلك .