في تلك الليلة، اخد خالد درعه، وسلاحه، و فرسه وانطلق إلى المدينة. وفي الطريق قابل عمرو بن العاص وعثمان بن طلحة (ابن حامل رابة قريش في غزوة احد) اللذين كانا متوجهين الى المدينة لنفس الغاية، وقد استغربوا امر ذهابهم للمدينة لان كل واحد منهم كان يعتبر الاثنين الآخرين من الد"اعداء المسلمين. وصل الثلاثة الى المدينة في الحادي والثلاثين من ايار عام 929 م و الأول من صفر عام 8 هجرية)، وذهبوا الى منزل النبي. دخل خالد أولا واسلم، ثم تبعه عمرو ثم عثمان، وقد رحب بهم النبي؛ وصفيح عن عداوتهم السابقة، وهم الآن يستطيعون أن يبدؤوا صفحة بيضاء و كان خالد وعمرو بن العاص المع عقلين عسكريين في زمانهما، ودخولهما الاسلام حقق النصر للمسلمين في السنوات التالية."

كان خالد، الذي بلغ الآن الثالثة والأربعين، مسرورة لوجوده في المدينة. فقابل اصدقاءه القدامى ووجد أنه موضع حفاوة وتكريم من الجميع.

وتم نسيان النزاعات القديمة. وسادت المدينة روح جديدة - انها روح الرجال الطلائع. وعم النشاط، والترقب الممزوج بالأمل، والحماسة: والتفاؤل و أرجاء المدينة، وتفاعل خالد بهذا الجو الذي لمس شغاف قلبه، و كان سعيدا بالدين الجديد.

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