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