Hazrat ‘Amr bin ‘Abasah (radhiyallahu ‘anhu) says:
From the very beginning, I disassociated myself from idol worship and I was completely averse to it. I understood and knew that idols could neither benefit nor harm and were mere pieces of stone.

On one occasion, I met a scholar from the Ahl-e-Kitaab (people of the scriptures i.e. Jews or Christians) and asked him which religion was the best and most virtuous. The scholar replied, “A man will soon appear in Makkah. His religion will be the best religion. He will invite people away from idolatry towards the oneness of Allah. If you happen to find him, ensure that you follow him.”

From that moment, the city of Makkah was constantly in my thoughts. I would enquire regarding the news of Makkah from every person going to Makkah or returning from it until I finally heard of Rasulullah’s (sallallahu ‘alaihi wasallam) appearance.

As soon as I heard of Rasulullah’s (sallallahu ‘alaihi wasallam) appearance, I went to Makkah and met him in secret. On meeting him, I asked, “Who are you?” He replied, “I am the messenger of Allah.” I asked, “Did Allah Ta‘ala send you as the Nabi?” Rasulullah (sallallahu ‘alaihi wasallam) replied in the affirmative. I then asked, “What message did Allah Ta‘ala send you with?” Rasulullah (sallallahu ‘alaihi wasallam) replied, “Allah Ta‘ala sent me with the message that you should believe in Him as one god and not ascribe any partners to him. You should destroy idols and maintain family ties.”

I then enquired, “In regard to this deen, who is with you?” He replied, “A free man and a slave (referring to Hazrat Abu Bakr (radhiyallahu ‘anhu) and Hazrat Bilaal (radhiyallahu ‘anhu)).” I submitted, “I am also your follower and I wish to remain with you.” Rasulullah (sallallahu ‘alaihi wasallam) advised, “For now, return to your home. When you learn of my deen becoming dominant in the land, you may return.”

I thus embraced Islam and returned home, and continued to enquire regarding news of Rasulullah (sallallahu ‘alaihi wasallam). When Rasulullah (sallallahu ‘alaihi wasallam) migrated to Madinah Munawwarah, I presented myself before him and asked, “O Prophet of Allah (sallallahu ‘alaihi wasallam)! Do you remember me?” Rasulullah (sallallahu ‘alaihi wasallam) replied, “Yes, you are the person who approached me while I was in Makkah.” I responded, “Yes, I am the same person. O Prophet of Allah (sallallahu ‘alaihi wasallam)! Teach me something… (Rasulullah (sallallahu ‘alaihi wasallam) then taught him deen).”

(Seeratul Mustafa 1/169-170)