Khalid bin Walid
Awal karir militernya > Mualaf dan pengabdian di bawah Muhammad

Pada tahun 6 H (sekitar tahun 627) atau 8 H (sekitar tahun 629), Khalid memeluk Islam di hadapan Muhammad bersama dengan Amr bin al-As dari suku Quraisy; sejarawan modern Michael Lecker berkomentar bahwa kisah-kisah yang menyatakan bahwa Khalid dan Amr masuk Islam pada tahun 8 H "mungkin lebih dapat dipercaya". Sejarawan Akram Diya Umari menyatakan bahwa Khalid dan Amr memeluk Islam dan pindah ke Madinah setelah Perjanjian Hudaibiyyah, tampaknya setelah kaum Quraisy membatalkan tuntutan ekstradisi orang-orang yang baru mualaf ke Makkah. Setelah ia menjadi mualaf, Khalid "mulai mengabdikan semua kegiatan militernya yang cukup besar untuk menyokong negara Muslim yang baru", demikian menurut sejarawan Hugh N. Kennedy.
Khalid berpartisipasi dalam ekspedisi ke Mu'ta di Yordania modern yang diperintahkan oleh Muhammad pada bulan September 629. Tujuan dari penyerbuan itu kemungkinan untuk mendapat harta rampasan setelah mundurnya tentara Persia Sasaniyah dari Suriah setelah kekalahannya dari Kekaisaran Bizantium pada bulan Juli. Detasemen Muslim ini dipukul mundur oleh pasukan Bizantium yang sebagian besar terdiri dari suku-suku Arab yang dipimpin oleh komandan Bizantium, Theodorus, dan beberapa komandan Muslim berpangkat tinggi terbunuh. Khalid mengambil alih komando pasukan setelah kematian para komandan yang ditunjuk dan, dengan penuh kesulitan, mengawasi penarikan mundur kaum Muslim dengan aman.  Muhammad menghadiahi Khalid dengan menganugerahkan kepadanya gelar kehormatan Saifullah ('Pedang Allah').
Pada bulan Desember 629 atau Januari 630, Khalid mengambil bagian dalam penaklukan Makkah oleh Muhammad, yang menyebabkan sebagian besar suku Quraisy memeluk Islam. Dalam pertempuran itu, Khalid memimpin kontingen nomaden yang disebut muhajirat al-arab ('emigran Badui'). Dia memimpin salah satu dari dua serangan utama ke dalam kota tersebut dan pertempuran berikutnya dengan suku Quraisy, tiga dari anak buahnya terbunuh sementara dua belas orang Quraisy terbunuh, menurut Ibnu Ishaq, penulis biografi abad ke-8 dari Muhammad. Khalid memerintahkan Badui Bani Sulaym berposisi di garda depan pada Pertempuran Hunain pada akhir tahun itu. Dalam konfrontasi tersebut, kaum Muslimin, yang diperkuat oleh masuknya para mualaf suku Quraisy, mengalahkan suku Tsaqif—saingan lama suku Quraisy yang berbasis Ta'if—dan sekutu-sekutu nomaden mereka, suku Hawazin. Khalid kemudian ditunjuk untuk menghancurkan berhala al-Uzza, salah satu dewi yang disembah dalam agama Arab pra-Islam, di daerah Nakhla antara Makkah dan Ta'if.
Khalid kemudian dikirim untuk mengajak Bani Jadhima masuk Islam di Yalamlam, sekitar 80 kilometer di selatan Makkah, tetapi sumber-sumber tradisional Islam menyatakan bahwa ia menyerang suku tersebut secara ilegal. Dalam versi Ibnu Ishaq, Khalid membujuk para anggota suku Jadhima untuk melucuti senjata dan memeluk Islam, yang kemudian ditindaklanjuti dengan mengeksekusi sejumlah anggota suku sebagai pembalasan dendam atas pembunuhan pamannya, Fakih bin al-Mughirah, yang dilakukan oleh suku Jadhima sebelum Khalid memeluk Islam. Dalam narasi Ibnu Hajar al-'Asqalani (w. 1449), Khalid secara keliru menganggap bahwa suku-suku tersebut menjadi mualaf sebagai penolakan atau penghinaan terhadap Islam karena ketidaktahuannya tentang aksen Jadhima sehingga ia menyerang mereka. Dalam kedua versi tersebut, Muhammad menyatakan dirinya tidak bertanggung jawab atas tindakan Khalid tetapi tidak memberhentikan atau menghukumnya.
Kemudian pada tahun 630, ketika Muhammad berada di Tabuk, ia mengirim Khalid untuk merebut kota pasar oasis Dumat al-Jandal. Khalid berhasil membuatnya menyerah dan menjatuhkan hukuman berat kepada penduduk kota. Salah satu dari para petingginya, Ukaidir bin Abdul Malik as-Sakuni dari suku Kindah, diperintahkan oleh Khalid untuk menandatangani perjanjian kapitulasi dengan Muhammad di Madinah. Pada bulan Juni 631, Khalid diutus oleh Muhammad sebagai kepala dari 480 orang untuk mengundang suku campuran Kristen dan politeis Balharits dari Najran untuk memeluk Islam. Suku tersebut mualaf dan Khalid mengajarkan mereka tentang al-Qur'an dan hukum-hukum Islam sebelum kembali kepada Muhammad di Madinah dengan delegasi Balharits.