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