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