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