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