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