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