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