كتب الخليفة إلى خالد يأمره بأن يستخلف على العراق ويتجه بخيرة جنده إلى الشام، وصدع خالد بأمر الخليفة واتجه إلى الشام في تسعة آلاف مقاتل من خيرة الجند، حيث اختار أصحاب رسول ﷺ -وضن بهم على المثنى بن حارثة خليفته على العراق، وغضب مثنى لذلك التقسيم وقال: "والله لا أقيم إلا على إنفاذ أمر أبي بكر، وبالله ما أرجوا من النصر إلا بأصحاب النبي ﷺ" [٧] فلما سمع خالد منه ذلك أرضاه وأسكته، وأراد خالد أن يغادر العراق وهو مطمئن فرد النساء والضعفاء إلى المدينة حتى لا ينشغل بهم المثنى عند منازلة عدوه.
وقطع خالد بجيشه بادية الشام المعروفة ببادية السماوة وهو طريق لم يعبره جيش قط قبل جيش خالد، وذلك لوعورته وقلة الماء فيه، وتعرض من يسلكه للهلاك بالعطش والضياع، وإنما صمم خالد على اختراق هذه البادية رغم تحذير العارفين بها لأنه كان يريد أن يباغت العدو فينزل خلفهم حتى لا يحبسوه عن إغاثة المسلمين.
وبالعزم والإيمان اخترق خالد وجيشه تلك البادية، وغامر هذه المغامرة، وقطعها في خمسة أيام، وكلما مر بجماعة من أعداء المسلمين قاتلهم وتغلب عليهم وغنم منهم حتى وصل اليرموك في آخر ربيع الآخر من السنة الثالثة عشر من الهجرة.