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