فأتو بمسيلمة إلى رسول الله -صلى الله عليه وسلم- يستر بالثياب، ورسول الله -صلى الله عليه وسلم- جالس مع أصحابه، في يده عسيب من سعف النخل، فلمَّا انتهى إلى رسول الله -صلى الله عليه وسلم- وهم يسترونه بالثياب -كلَّمه وسأله، فقال له رسول الله -صلى الله عليه وسلم: "لو سألتني هذا العسيب الذي في يدي ما أعطيتك".

وذكر حديثه ابن إسحاق على غير ذلك, فقال: حدَّثني شيخ من أهل اليمامة من بني حنيفة: أنَّ وفد بني حنيفة أتوا رسول الله -صلى الله عليه وسلم- وخلَّفوا مسيلمة في رحالهم، فلمَّا أسلموا ذكروا له مكانه، فقالوا: يا رسول الله، إنا قد خَلَّفنا صاحبنا في رحالنا وركابنا يحفظها لنا، فأمر له رسول الله -صلى الله عليه وسلم- بما أمر به للقوم، وقال لهم: إنه ليس بشركم مكانًا، يعني: لحفظه ضيقة أصحابه،