سعيد إلى أبي بكر بذلك، وبنزول من استنفرت الروم، ونفر إليهم من بهراء وكلب وسليح وتنوخ ولخم وجذام وغسان من دون زيزاء بثلاث، فكتب إليه أبو بكر: أن أقدم ولا تحجم واستنصر الله، فسار إليهم خالد، فلما دنا منهم تفرقوا وأعروا منزلهم، فنزله ودخل عامة من كان تجمع له في الإسلام، وكتب خالد إلى أبي بكر بذلك، فكتب إليه أبو بكر:

أقدم ولا تقتحمن حتى لا تؤتى من خلفك فسار فيمن كان خرج معه من تيماء وفيمن لحق به من طرف الرمل، حتى نزلوا فيما بين آبل وزيزاء والقسطل، فسار إليه بطريق من بطارقة الروم، يدعى باهان، فهزمه وقتل جنده، وكتب بذلك إلى أبي بكر واستمده وقد قدم على أبي بكر أوائل مستنفري اليمن ومن بين مكة واليمن، وفيهم ذو الكلاع، وقدم اليه عكرمة قافلا وغازيا فيمن كان معه من تهامة وعمان والبحرين والسرو.

فكتب لهم أبو بكر إلى أمراء الصدقات أن يبدلوا من استبدل، فكلهم استبدل، فسمي ذلك الجيش جيش البدال فقدموا على خالد بن سعيد، وعند ذلك اهتاج أبو بكر للشأم، وعناه أمره وقد كان أبو بكر رد عمرو بن العاص على عماله كان رسول الله ص ولاها إياه من صدقات سعد هذيم، وعذرة ومن لفها من جذام، وحدس قبل ذهابه إلى عمان فخرج إلى عمان وهو على عدة من عمله، إذا هو رجع فأنجز له ذلك أبو بكر.

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