وكان ذلك قبل حجة الوداع .. حيث أرسله النبي صلة الله عليه وسلم إلى زبيد ..

قال البراء رضي الله عنه: بعثنا رسول الله صلى الله عليه وسلم مع خالد بن الوليد إلى اليمن، قال: ثم بعث عليا بعد ذلك مكانه فقال: «مر أصحاب خالد، من شاء منهم أن يعقب معك فليعقب، ومن شاء فليقبل» فكنت فيمن عقب معه، قال: فغنمت أواق ذوات عدد ..

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

لم يكن خالد يغيب عن مشاهد النبي صلى الله عليه وسلم، فكان معه في مواقفه كلها.

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

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