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