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