طريقا فمر بها فاتبعه خالد بن أسيد ومر بالطائف فاتبعه عبدالرحمن بن أبي العاص ثم مضى حتى إذا حاذى بجرير بن عبدالله ضمه إليه وانضم إليه عبدالله بن ثور حين حاذى به ثم قدم على أهل نجران فانضم إليه فروة بن مسيك وفارق عمرو بن معدي كرب قيسا وأقبل مستخفيا حتى دخل على المهاجر على غير أمان فأوثقه المهاجر وأوثق قيسا وكتب بحالهما إلى أبي بكر وبعث بهما إليه
أخبرنا أبو البركات بن المبارك أنا أحمد بن الحسن بن خيرون أنا عبدالملك بن محمد أنا أبو علي بن الصواف نا محمد بن عثمان بن أبي شيبة نا المنجاب أنا خلاد الأحول عن خالد بن سعيد عن أبيه قال
بعث النبي صلى الله عليه وسلم خالد بن سعيد بن العاص إلى اليمن وقال له إن مررت بقرية فلم تسمع أذانا فاسبهم قال فمر ببني زبيد فلم يسمع أذانا فسباهم فأتاه عمرو بن معدي كرب فكلمه فيهم فوهبهم له خالد قال فوهب له عمرو سيفه الصمصامة فلما تسلحه خالد ومضى نظر عمرو بن معدي كرب في قفاه فقال
( 00000000000 ** على الصمصامة السيف السلام )
ليس عنده تمام البيت
( بأنه لم أخنك ولم تخني ** ولكن المواهب للكرام )
( وكنت إذا نهضت به لقوم ** يجاوب صوب نوح بالندام )
قال ابن إسحاق فأقام عمرو بن معدي كرب في قومه من زبيد وعليهم فروة بن مسيك فلما توفي رسول الله صلى الله عليه وسلم ارتد عمرو فقال عمرو حين ارتد
( وجدنا ملك فروة شر ملك ** حمارا ساف منخره بقذر )
( وكنت إذا رأيت أبا عمير ** أرى الحولاء من خبث وغدر )