وأسلم محمد بن مسلمة بالمدينة, على يد مصعب بن عمير, وذلك قبل إسلام أسيد بن الحضير, وسعد بن معاذ.
وآخى رسول الله صلى الله عليه وسلم بين محمد بن مسلمة, وأبي عبيدة بن الجراح، وشهد محمد بدرا، وأحدا, وكان فيمن ثبت مع رسول الله صلى الله عليه وسلم يومئذ حين ولى الناس، وشهد الخندق, والمشاهد كلها مع رسول الله صلى الله عليه وسلم, ما خلا تبوك، فإن رسول الله استخلفه على المدينة حين خرج إلى تبوك، وكان محمد فيمن قتل كعب بن الأشرف، وبعثه رسول الله صلى الله عليه وسلم إلى القرطاء, وهم من بني أبي بكر بن كلاب, سرية في ثلاثين راكبا من أصحاب رسول الله صلى الله عليه وسلم, فسلم وغنم، وبعثه أيضا إلى ذي القصة سرية في عشرة نفر.
4424- أخبرنا محمد بن عمر, قال: أخبرني معاذ بن محمد، عن عاصم بن عمر بن قتادة، قال: لما خرج رسول الله صلى الله عليه وسلم إلى عمرة القضية, فانتهى إلى ذي الحليفة, قدم الخيل أمامه وهي مئة فرس، واستعمل عليها محمد بن مسلمة.
4425- أخبرنا محمد بن عمر, قال: حدثني إبراهيم بن جعفر، عن أبيه، قال: كان محمد بن مسلمة يقول: يا بني، سلوني عن مشاهد النبي عليه السلام ومواطنه؛ فإني لم أتخلف عنه في غزوة قط، إلا واحدة، في تبوك، خلفني على المدينة، وسلوني عن سراياه صلى الله عليه وسلم، فإنه ليس منها سرية تخفى علي، إما أن أكون فيها، أو أن أعلمها حين خرجت.
أخبرنا إسماعيل بن إبراهيم الأسدي، عن أبي حيان التيمي، عن عباية بن رفاعة بن رافع، في حديث رواه محمد بن مسلمة، وكان رجلا أسود طويلا عظيما. قال: وزادنا محمد بن عمر في صفته, فقال: كان معتدلا أصلع.
4426- أخبرنا يزيد بن هارون، قال: أخبرنا هشام بن حسان، عن الحسن؛ أن رسول الله صلى الله عليه وسلم أعطى محمد بن مسلمة سيفا, فقال: قاتل به المشركين ما قوتلوا، فإذا رأيت المسلمين قد أقبل بعضهم على بعض فأت به أحدا, فاضربه به حتى تقطعه، ثم اجلس في بيتك حتى تأتيك يد خاطئة، أو منية قاضية.