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