فلما بلغ كعبا الكتاب ضاقت به الأرض وأشفق على نفسه، وأرجف به من كان في حاضره من عدوه فقالوا: هو مقتول. فلما لم يجد من شيء بدا قال قصيدته التي يمدح فيها رسول الله ويذكر فيها خوفه وإرجاف الوشاة به من عدوه، ثم خرج حتى قدم المدينة فنزل على رجل كانت بينه وبينه معرفة من جهينة كما ذكر، فغدا به إلى رسول الله صلى الله عليه وسلم، ثم أشار له إلى رسول الله فقال: هذا رسول، فقم إليه واستأمنه، فذكر لي أنه قام إلى رسول الله حتى جلس إليه فوضع يده في يده وكان رسول الله لا يعرفه فقال: يا رسول الله إن كعب بن زهير جاء ليستأمنك تائبا مسلما، فهل أنت قابل منه إن أنا جئتك به؟ قال رسول الله:"نعم". قال أنا يا رسول الله كعب بن زهير.

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

بانت سعاد فقلبي اليوم متبول ... متيم إثرها لم يفد مكبول

وما سعاد غداة البين إذ رحلوا ... إلا أغن غضيض الطرف مكحول

هيفاء مقبلة، عجزاء مدبرة ... لا يشتكي قصر منها ولا طول

تمشي الغواة بجنبيها وقولهم ... إنك يا ابن أبي سلمى لمقتول

وقال كل خليل كنت آمله ... لا ألهينك إني عنك مشغول

فقلت خلوا سبيلي لا أبا لكم ...

فكل ما قدر الرحمن مفعول