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