صبأنا، ثم أرسله صلى الله عليه وسلم إلى أُكَيْدِر ابن صاحب دومة الجندل، عبد الملك النصراني، وقال: إنك ستجده ليلا يصيد البقر، فوجده كذلك، فأسره.

قال النووي: وأحضره عند رسول الله صلى الله عليه وسلم، فصالحه على الجزية، وردَّه إلى بلده، ثم أرسله صلى الله عليه وسلم إلى بني عبد المدان بنجران، فأسلموا، وذكر النووي أنه أرسله سنة عشر إلى بني الحارث بن كعب بن مذحج، فقدم معه رجال منهم، فأسلموا، ورجعوا إلى قومهم.

ذكر سيرته في عهد أبي بكر رضي الله عنه:

لمَّا كانت خلافة أبي بكر رضي الله عنه، شهد خالد وقعة اليرموك، وارتدت في أيامه العرب، فأرسل الجيوش إليهم، فأبادوا مَن أصرَّ منهم على كفره، وأرسل خالدا إلى العراق، وعمرو بن العاص إلى فلسطين، ويزيد بن أبي سفيان، وأبا عبيدة، وشرحبيل بن حسنة إلى الشام، وفي أيامه ادَّعت سجاح بنت الحارث بن سويد التميمية النبوّة، وقصدت مُسيلمة الكذاب، وباتت عنده ثلاث ليالٍ يزني بها، وكان قد قدم على النبي صلى الله عليه وسلم، ثم ارتدَّ بمن معه، وادّعى النبوّة باليمامة استقلالا، ثم مشاركة معه صلى الله عليه وسلم، وجهز إليه وإليهم أبو بكر رضي الله عنه جيشا، وأمَّر عليهم خالدا، وجرى بين الفريقين قتال شديد، ثم قُتل مسيلمة، وأمَّا سجاح فإنها لم تزل في أخوالها بني تغلب حتى أتت معاوية عاما بويع فيه، فأسلمت، وحسُن إسلامها.

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