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