الخرزج، وهو من ولد يوسف بن يعقوب عليهما السلام. أسلم عند قدوم النبى صلى الله عليه وسلم المدينة. ويحدثنا البخارى عن قصة إسلامه فيقول فى ضمن حديث ساقه فى باب الهجرة: " ... فلما جاء نبى الله صلى الله عليه وسلم، جاء عبد الله بن سلام فقال: أشهد أنك رسول الله، وأنك جئتَ بحق، وقد علمت اليهود أنى سيدهم وابن سيدهم، وأعلمهم وابن أعلمهم، فادعهم فاسألهم عنى قبل أن يعلموا أنى قد أسلمت، فإنهم إن يعلموا أنى قد أسلمتُ قالوا فىَّ ما ليس فىّ، فأرسل نبى الله صلى الله عليه وسلم، فأقبلوا فدخلوا عليه، فقال لهم رسول الله صلى الله عليه وسلم: "يا معشر اليهود؛ ويلكم، اتقوا الله، فواللهِ الذى لا إله إلا هو، إنكم لتعلمون أنى رسول الله حقاً، وأنى جئتكم بحق فأسلموا"، قالوا: ما نعلمه، قالوا للنبى صلى الله عليه وسلم، قالها ثلاث مرات، قال: "فأى رجل فيكم عبد الله بن سلام"؟ قالوا: ذلك سيدنا وابن سيدنا، وأعلمنا وابن أعلمنا، قال: "أفرأيتم إن أسلم"؟ قالوا: حاشا لله، ما كان ليسلم، قال: "أفرأيتم إن أسلم"؟ قالوا: حاشا لله ما كان ليسلم، قال: " أفرأيتم إن أسلم"؟ قالوا: حاشا لله ما كان ليسلم، قال: "يابن سلام.. اخرج عليهم"، فخرج، فقال: يا معشر اليهود؛ اتقوا الله، فواللهِ الذى لا إله إلا هو، إنكم لتعلمون أنه رسول الله وأنه جاء بحق، فقالوا: كذبت، فأخرجهم رسول الله صلى الله عليه وسلم".
قيل: وكان اسمه الحصين، فسماه النبى صلى الله عليه وسلم: "عبد الله"، وشهد له بالجنة. ونجد البخارى رضى الله عن - عند الكلام عن مناقب الأنصار - يُفرد لعبد الله بن سلام باباً مستقلاً فى مناقبه، فروى فيما روى من ذلك بإسناده إلى سعد بن أبى وقاص أنه قال: ما سمعتُ النبى صلى الله عليه وسلم يقول لأحد يمشى على الأرض إنه من أهل الجنة إلا لعبد الله بن سلام، وقال: فيه نزلت هذه الآية: {وَشَهِدَ شَاهِدٌ مِّن بني إِسْرَائِيلَ} [الأحقاف: ١٠] ... الآية.
ومما يُذكر عنه رحمه الله: أنه وقف خطيباً فى المتألبين على عثمان رضى الله عنه يدافع عنه، ويُخذِّل الثائرين، فقد روى عبد الملك بن عمير عن ابن أخى عبد الله بن سلام، قال: لما أريد قتل عثمان رضى الله عنه، جاء عبد الله بن سلام، فقال له عثمان: ما جاءبك؟ قال: جئتُ فى نصرك، قال: أخرج إلى الناس فاطردهم عنى، فإنك خارج خير لى منك داخل، فخرج عبد الله إلى الناس فقال: يا أيها الناس؛ إنه كان اسمى فى الجاهلية فلاناً، فسمانى رسول الله صلى الله عليه وسلم: عبد الله، ونزلت فىَّ آيات من كتاب الله عَزَّ وجَلَّ، نزل فىَّ: {وَشَهِدَ شَاهِدٌ مِّن بني إِسْرَائِيلَ على مِثْلِهِ فَآمَنَ واستكبرتم} .. ونزل فى: {قُلْ كفى بالله شَهِيداً بَيْنِي وَبَيْنَكُمْ وَمَنْ عِندَهُ عِلْمُ الكتاب} [الرعد: ٤٣] .. إن لله سيفاً مغموداً، وإن الملائكة قد جاورتكم فى بلدكم هذا الذى نزل فيه رسول الله صلى الله عليه وسلم، فاللهَ اللهَ فى هذا الرجل أن تقتلوه، فوالله لئن قتلتموه لتطردن جيرانكم من الملائكة وليُسلَنَّ سيف الله المغمود فيكم فلا يُغمد إلى يوم القيامة. قالوا: اقتلوا اليهودى.. وقتلوا عثمان"..