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