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