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