این تنها جنایتی نبود که «خالد» در دوران زندگی به ظاهر اسلامی خود مرتکب شده، بلکه در دوران خلافت «ابی بکر» شدیدتر از آن را انجام داد. اجمال آن این است که برخی از قبایل پس از رحلت رسول خدا راه ارتداد پیش گرفتند و یا به تعبیر صحیح خلافت ابی بکر را به رسمیت نشناختند و از دادن زکات ابا ورزیدند. خلیفه وقت، گروهی را به اطراف فرستاد تا مرتدان را سرکوب سازند.
«خالد بن ولید» به بهانه ارتداد به قبیله «مالک بن نویره» حمله برد و «مالک» و تمام افراد قبیله‌اش، برای دفاع آماده بودند و همگی می‌گفتند که ما مسلمانیم سربازان اسلام نباید به ما هجوم کنند. خالد از طریق مکر و حیله همه آن‌ها را خلع سلاح کرد و