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