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