قال ابن سعد: أسلم محمد بن مسلمة على يد مصعب بن عمير، قبل إسلام سعد بن معاذ. قال: وآخى رسول الله صلى الله عليه وسلم بينه وبين أبي عبيدة، واستخلفه على المدينة عام تبوك (1).
حماد بن سلمة، عن ابن جدعان، عن أبي بردة، قال: مررنا بالربذة، فإذا فسطاط محمد بن مسلمة، فقلت: لو خرجت إلى الناس، فأمرت ونهيت؟ فقال: قال لي النبي صلى الله عليه وسلم: " يا محمد، ستكون فرقة وفتنة واختلاف، فاكسر سيفك، واقطع وترك، واجلس في بيتك ". ففعلت ما أمرني (2).
شعبة، عن أشعث، عن أبي بردة، عن ضبيعة (3): قال حذيفة: إني لأعرف رجلا لا تضره الفتنة. قال: فإذا فسطاط لما أتينا المدينة، وإذا محمد ابن مسلمة (4).
قال ابن يونس: شهد محمد فتح مصر، وكان فيمن طلع الحصن مع الزبير. قال عباية بن رفاعة: كان محمد بن مسلمة، أسود طويلا عظيما.