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