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