فقلت له: أيها الملك, لو ظننت أنك تكره ما قلت ما سألتكه, قال: فاستحيا, وقال: ياعمرو, تسألني أن أعطيك رسول رسول الله صلى الله عليه وسلم، من يأتيه الناموس الأكبر, الذي كان يأتي موسى، والذي كان يأتي عيسى بن مريم لتقتله؟!

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