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