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