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