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