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