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