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