ثم إن سلمان فزع بطلب الراهب ، فلقيه رجلان من العرب من كلب ، فسألهما هل رأيتما الراهب ؟ فأناخ أحدهما راحلته قال: نعم [] راعي الصرمة هذا ، فحمله فانطلق به إلى المدينة قال سلمان: فأصابني من الحزن شيء لم يصبني مثله قط ، فاشترته امرأة من جهينة فكان يرعى عليها هو وغلام لها يتراوحان الغنم ، هذا يوماً وهذا يوماً ، وكان سلمان يجمع الدراهم ينتظر خروج محمد صلى الله عليه وسلم. فبينما هو يوماً يرعى إذ أتاه صاحبه بعقبة فقال له: أشعرت أنه قد قدم المدينة اليوم رجل يزعم أنه نبي ؟! فقال له سلمان: أقم فِي الغنم حتى آتيك.
فهبط سلمان إلى المدينة فنظر إلى النبي صلى الله عليه وسلم ودار حوله ، فلما رآه النبي صلى الله عليه وسلم عرف ما يريد ، فأرسل ثوبه حتى خرج خاتمه ، فلما رآه أتاه وكلمه ، ثم انطلق فاشترى بدينار ببعضه شاة فشواها وببعضه خبزاً ، ثم أتاه به فقال: ماهذه ؟ قال سلمان: هذه صدقة. قال: لا حاجة لي بها فأخرجها فليأكلها المسلمون. ثم انطلق فاشترى بدينار آخر خبزاً ولحماً ، ثم أتى به النبي صلى الله عليه وسلم فقال: ما هذا ؟ قال: هذه هدية. قال: فاقعد فكل. فقعد فأكلا منها جميعا.
فبينما هو يحدثه إذ ذكر أصحابه فأخبره خبرهم ، فقال: كانوا يصلون ويصومون ويؤمنون بك ، ويشهدون أنك ستبعث نبياً ، فلما فرغ سلمان من ثنائه عليهم قال له نبي الله صلى الله عليه وسلم:"يا سلمان هم من أهل النار"فاشتد ذلك على سلمان وقد كان قال له سلمان: لو أدركوك صدقوك واتبعوك. فأنزل الله هذه الآية {إن الذين آمنوا والذين هادوا والنصارى والصابئين من آمن بالله واليوم الآخر} .