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