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

أعزي شدي شدة لا تكذبي ... أعزي فالقي للقناع وشمري

أعزي إن لم تقتلي اليوم خالدا ... فبوئي بذنب عاجل فتنصري

وأقبل خالد بالسيف إليها وهو يقول:

يا عز كفرانك لا سبحانك ... إني وجدت الله قد أهانك

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