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