Hudeybiye anlaşmasının ılıman ikliminde Halid de kendince bir iç hesaplaşmaya girişmişti. Bunlar başlangıçta bir askerin kendini sigaya çekmesi şeklindeydi. Asker olarak yeteneklerinin farkındaydı ama bir türlü içine sindirebileceği bir zaferle kucaklaşamamıştı. Her nasılsa zafer ondan kaçıyordu! Uhud’da,tüm ustaca manevralarına rağmen Müslümanlara son darbeyi vuramamıştı. Peygamberin askerlerini sahaya knumlandırmasına ve dezavantajlarına rağmen savaşı Kureyşlilerin üzerine yıkma tarzına hayran olmuştu. Hendek Savaşı’nda da zafer Kureyşlleri sıyırıp geçmişti. Kureyşliler sayıca ve mühimmat olarak o kadar üstündü ki zafere kesin gözüyle bakılıyordu. Oysa Kureyşliler aslanlar gibi gittikleri cepheden fareler gibi döneceklerdi. Hudeybiye’de de Müslümanların yolunu kesmeye çalıştığında Peygamber yine kendisini şık bir manevrayla safdışı bırakmıştı. Halid bir yandan bu düşmanını ele geçirmeye çalışırken, diğer yandan da Peygamberin kumandanlığına, karakterine ve açıkçası bir başkasına benzerini göremediği kişisel hasetlerine de hayanlık duymadan edemiyordu. Ama hepsinden önce kendini savaşarak ifade eden Halid, bir türlü zaferle tanışamıyordu. Kureyş’in kendisine tattırdığı hezimetten başkası değildi. kureyşlilrle birlikte büyük zaferlere kavuşamayacağı düşüncesi maceracı ruhunu kemirmeye başlamıştı. Belki de Peygambere katılmalıydı, kim bilir. Bu arada Medine çıkışlı askeri seferlerle ilgili haberler Halid’in de kulağına geliyordu. Uhud Savaşı ile hac dönemi arasında Müslümanlar, büyük bir kısmından zaferle döndükleri yirmi sekiz sefere çıkmışlardı. Bunlar sadece İslam’ın siyasi sınırlarını genişletmekle almıyor aynı zamanda Müslümanlara zenginli de getiriyordu. Her ne zaman Müslümanların zaferiyle ilgili haberler Mekke’ye ulaşsa, Halid’in içinden hep aynı düşünce geçiyordu: ‘Keşke ben de onlarla cephede olsaydım!’ Peygamberi hac farizası esnasında gözlemleyen Halid’in zihninden geçen ‘zafer özlemi’, bir süre sonra yerini iç hesaplaşmaya bırakacaktı. Hiçbir zaman bu konularda derinlemesine düşünmemiş, Kabe’nin putlarına olan ilgisi de üstünkörü olmaktan öte geçmemişti. Her zaman zihninin bir yerinde, doldurulmayı bekleyen bir alan bırakmıştı. Şimdi ciddi bir şekilde bu meseleler üzerine kafa yoruyor, ama düşüncelerini kimseyle paylaşamıyordu. Aslında paylaşamadığı, ‘İslam’ın hak din olduğu gerçeği’ne her gün biraz daha yaklaşmakta olduğuydu. İslam hakkında kesin kararını vermişti. Büyük İslam düşmanı Ebu Cehil’in oğlu İkrime başta olmak üzere diğer yakınlarıyla bir araya geldi ve tepki alacağını bilmesine rağmen kararını açıkladı: Müslüman olacaktı. O gece Halid, kılıcını ve atını alarak Medine yoluna düştü. Yolda, kendisi gibi Müslüman olma yolunda at süren Osman bin Talha ile karşılaştı. Birlikte, yeni bir dünyaya atım attılar. İslam Peygamberinden özür ve af dileyen Halid, İslam ile şereflenmişti. O andan itibaren gücünü, savaşçılığını ve askeri dehasını İslam adına kullanacak, bu uğurda gösterdiği kahramanlıklardan dolayı da Hz. Muhammed’den ‘Seyfullah’ (Allah’ın kılıcı) unvanını almaya hak kazanacaktı.