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