قال محمد بن سعد: بعثه عند منصرفه من الجعرانة «١» إليه، يدعوه إلى الإسلام، وكتب إليه كتابا. فكتب إلى رسول الله صلّى الله عليه وسلّم بإسلامه وتصديقه، و «أنى قرأت كتابك على أهل هجر، فمنهم من أحبّ الإسلام، وأعجبه ودخل فيه، ومنهم من كرهه، وبأرضى مجوس ويهود، فأحدث إلىّ فى ذلك أمرك» فكتب إليه رسول الله صلّى الله عليه وسلّم: «إنك مهما تصلح فلن نعزلك عن عملك، ومن أقام على يهوديته أو مجوسيته فعليه الجزية، وبألا تنكح نساؤهم ولا تؤكل ذبائحهم «٢» » .
وكان رسول الله صلّى الله عليه وسلّم بعث أبا هريرة مع العلاء بن الحضرمى، وأوصاه به خيرا، وكتب رسول الله صلّى الله عليه وسلّم إلى العلاء فرائض الإبل، والبقر والغنم، والثمار والأموال، فقرأ العلاء كتابه على الناس وأخذ صدقاتهم.
وبعث صلّى الله عليه وسلّم عمرو بن العاص إلى ملكى عمان.
قال محمد بن سعد: بعثه رسول الله صلّى الله عليه وسلّم فى ذى القعدة، سنة ثمان من مهاجره، إلى جيفر وعبد ابنى الجلندى «٣» ، وهما من الأزد، والملك منهما جيفر، يدعوهما إلى الإسلام، وكتب معه إليهما كتابا، قال عمرو: لما قدمت عمان عمدت إلى عبد، وكان أحلم الرجلين وأسهلهما خلقا، فقلت: إنى رسول رسول الله صلّى الله عليه وسلّم إليك وإلى أخيك، فقال: أخى المقدّم علىّ بالسّنّ والملك وأنا أوصلك إليه حتى تقرأ كتابك، فمكشت أياما ببابه، ثم دعانى فدخلت عليه