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