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

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

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

ومنها:

أمست سعاد بأرض لا يبلغها ... إلا العتاق النجيبات المراسيل

إلى أن قال:

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

وقال

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

فقلت: خلوا سبيلي لا أبا لكمو ... فكل ما قدر الرحمن مفعول

نبئت أن رسول الله أوعدني ... والعفو عند رسول الله مأمول