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