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

وروي أنه قال له:"يا معاذ إنك تقدم على قوم أهل كتاب، وإنهم سائلوك عن مفاتيح الجنة، فأخبرهم أن مفاتيح الجنة لا إله إلا الله وأنها تخرق كل شيء حتى تنتهي إلى الله ولا تحجب دونه، من جاء به يوم القيامة مخلصا رجحت بكل ذنب". فقال معاذ: أرأيت ما سئلت عنه واختصم إلي فيه مما ليس في كتاب الله ولم أسمع منك سنة الله؟ فقال:"تواضع يرفعك الله، ولا تقضين إلا بعلم، فإن أشكل عليك أمر فسل ولا تستحي، واستشر ثم اجتهد، فإن الله إن علم من قلبك الصدق يوفقك. فإن التبس عليك فقف حتى تتنبه أو تكتب إلي فيه. واحذر الهوى فإنه قائد الأشقياء إلى النار. وعليك بالرفق"

وفي رواية أنه قال له لما بعثه إلى اليمن"كيف تقضي إذا عرض لك قضاء؟"قال: أقضي بكتاب الله. قال:"فإن لم تجد في كتاب الله؟"قال: فبسنة رسول الله. قال:"فإن لم تجد في سنة رسول الله؟"قال: اجتهد رأيي ولا آلو. قال فضرب رسول الله صلى الله عليه وسلم على صدره وقال:"الحمد لله الذي سدد رسول رسول الله لما يرضي رسول الله"رواه الترمذي وأبو داود والدارمي.