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

فركب عَمرو بن معديكرب حتى قدم المدينة، فقال حين دخلها وهو آخذ بزمام راحلته: من سيد أهل هذه البحيرة من بني عمرو بن عامر؟ فقيل له: سعد بن عُبادة، فأقبل يقود راحلته حتى أناخ ببابه، فقيل لسعد: عمرو بن معديكرب، فخرج إليه سعد فرحَّب به وأمر برَحْله فحط وأكرمه وحَبَاه، ثم رَاحَ به إلى رسول الله، صَلَّى الله عليه وسلم، فأسلم وأقام أيامًا، وأجازه رسول الله، صَلَّى الله عليه وسلم ،كما يجيز الوفد، وانصرف راجعًا إلى بلاده.