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