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