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