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