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

وكتب النبي - صلى الله عليه وسلم - كتابًا إلى ملك عمان جَيْفَر وأخيه عبد ابني الجُلَنْدَي، ونصه:"بسم الله الرحمن الرحيم من محمد رسول الله إلى جيفر وعبد ابني الجلندي، سلام على من اتبع الهدي، أما بعد: فإني أدعوكما بدعاية الإسلام، أسلما تسلما، فإني رسول الله - صلى الله عليه وسلم - إلى الناس كافة، لأنذر من كان حيًا ويحق القول على الكافرين، فإنكما إن أقررتما بالإسلام وليتكما، وإن أبيتما [أن تقرا بالإسلام] فإن ملككما زائل، وخيلي تحل بساحتكما، وتظهر نبوتي على ملككما".

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