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

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

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

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

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

ورغم هذا الخطإ، أشركه الرسول بعد ذلك في غزوة حنين، حيث جعله الرسول يومئذ قائدًا على بني سليم، وأصيب يومها إصابات بليغة. كما شارك خالد أيضًا في غزوة تبوك تحت قيادة الرسول، ومن هناك أرسله الرسول في سرية إلى دومة الجندل، فدخلها وأسر صاحبها أكيدر بن عبد الملك الذي صالحه الرسول على الجزية، وهدم صنمهم «وُدّ». في عام 10 هـ، بعث الرسول خالد بن الوليد في شهر ربيع الأول في سرية من أربعمائة مقاتل إلى بني الحارث بن كعب بنجران، وأمره أن يدعوهم إلى الإسلام قبل أن يقاتلهم ثلاثًا، فإن استجابوا له يقبل منهم ويقيم فيهم ويعلمهم دينهم، وإن لم يفعلوا يقاتلهم. لبّى بنو الحارث بن كعب النداء وأسلموا، فأقام خالد فيهم يعلمهم الإسلام. ثم كتب خالد إلى الرسول بذلك، فأمره أن يقيم فيهم يعلمهم، ثم ليقبل معه وفدهم، فوفدوا عليه يعلنون إسلامهم.

وبعد شهور، نقضت قريش أحد شروط الصلح، عندما هاجم بكر بن مناة بن كنانة حلفاء قريش بني خزاعة حلفاء الرسول. عندئذ توجه الرسول في جيش من عشرة آلاف مقاتل إلى مكة، وقسم الجيش إلى أربعة أقسام تولى بنفسه قيادة أحدها وأمّر الزبير بن العوام وسعد بن عبادة وخالد بن الوليد على الثلاثة الأخرى، وأمرهم أن يدخلوا مكة كلٌ من باب. فدخلوها كل من الباب الموكل إليه، ولم يلق أحدهم قتالاً إلا كتيبة خالد، حيث قاتله عكرمة بن أبي جهل وسهيل بن عمرو وصفوان بن أمية في جند جمعوه لقتال المسلمين، واستطاع خالد أن يظفر بهم، وقتل منهم عددًا. ثم أرسله الرسول في سرية من ثلاثين فارسًا لهدم العزى صنم جميع بني كنانة، فهدمها ثم رجع إلى الرسول، فأخبره فسأله الرسول إن كان قد رأى شيئًا، فرد بالنفي، فطلب منه الرسول أن يعود لأنه لم يهدمها. فرجع خالد وهو متغيظ فجرد سيفه، فخرجت إليه امرأة عريانة سوداء ناشرة الرأس، فضربها خالد فشقها نصفين ورجع إلى الرسول. فأخبره فقال: «نعم تلك العزى، وقد يئست أن تعبد ببلادكم أبدا!». وكان موضع العزى ومقر عبادتها في شِعب يعرف بشعب سُقام إلى الشمال الشرقي من مكة اتخذه المشركون حمىً لها.