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