وأرسلت بنو عبد القيس وفدها إلى المدينة برئاسة الجارود بن عمرو، فأسلم وأصحابه، كما قدم وفد بني حنيفة وفيهم مسيلمة بن حبيب الحنفي الكذاب، فتركه قومه في رحالهم وذهبوا لمقابلة الرسول صلى الله عليه وسلم، ولما أسلموا وقفلوا عائدين إلى ديارهم أعلن مسيلمة أنه قد أشرك في الأمر مع الرسول صلى الله عليه وسلم وراح يتلو عليهم سجعه الذي ظن أنه إنما يضاهي به القرآن (?) .

وقدم عدي بن حاتم الذي كان قد اعتنق النصرانية ولجأ إلى الشام إثر اتساع سلطان المسلمين، وقال له الرسول: «لعلك يا عدي إنما يمنعك من دخول في هذا الدين ما ترى من حاجتهم، فو الله ليوشكن المال أن يفيض فيهم حتى لا يوجد من يأخذه، ولعلك إنما يمنعك من دخول فيه ما ترى من كثرة عدوهم وقلة عددهم، فو الله ليوشكن أن تسمع بالمرأة تخرج من القادسية على بعيرها حتى تزور هذا البيت لا تخاف. ولعلك إنما يمنعك من دخول فيه أنك ترى أن الملك والسلطان في غيرهم، وأيمّ الله ليوشكن أن تسمع بالقصور البيض من أرض بابل قد فتحت عليهم» . وما لبث عدي أن أعلن إسلامه (?) .

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