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