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

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

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

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