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