قال ابن إسحاق، عَن عَبد الله بن أبي بكر بن محمد بن عَمرو بن حزم قدم عَمرو بن مَعدِي كَرِب على رسول الله صَلى الله عَلَيه وسَلم في وفد زبيد فأسلم وله قصة مع قيس بن المكشوح المرادي.
وذكر ابن سعد، عَن الواقدي، عَن عَبد الله بن عَمرو بن زهير، عَن محمد بن عمارة بن خزيمة قال قال عَمرو بن مَعدِي كَرِب لقيس بن مكشوح حين انتهى إليهم أمر النَّبيّ صَلى الله عَلَيه وسَلم قد ذكر لنا أن رجلا من قريش يُقَالُ لَهُ: محمد قد خرج بالحجاز يقول إنه نبي فانطلق بنا إليه حتى نعلم علمه فإن كان نبيا فلن يخفى علينا.
فأتى قيس فركب عَمرو إلى المدينة فنزل على سعد بن عبادة فأكرمه وراح به إِلَى النَّبِيِّ صَلى الله عَلَيه وسَلم فأسلم وأجازه النَّبيّ صَلى الله عَلَيه وسَلم فرجع إلى قومه فأقام فيهم مسلما مطيعا، وكان عليهم فروة بن مسيك فلما مات النَّبيّ صَلى الله عَلَيه وسَلم ارتد عمرو.
وذكر ذلك سيف في كتاب الردة وأن المهاجر بن أَبي أُمَيَّة أسر عَمرو بن مَعدِي كَرِب فأرسله إلى أبي بكر فعاود الإسلام.
قال الخطيب في المتفق والمفترق يقال إن له وِفَادَةٌ وقيل لم يلق رسول الله صَلى الله عَلَيه وسَلم وإنما قدم إلى المدينة بعد وفاته وحضر القادسية وأبلى فيها.