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