After learning information about Muhammad, Zayd made enquiries and decided to travel to Medina and meet him, taking a delegation of his people including Zurr ibn Sudoos, Malik ibn Jubayr, Aamir ibn Duwayn and others. When they reached Medina, they entered Masjid al-Nabawi while he was addressing his congregation. Zayd and his delegation were astonished by the attention of the Muslims and the effect of his words on them. Muhammad said:
"I am better for you than al-Uzza (one of the main idols of the Arabs in the pre-Islamic era) and everything else that you worship. I am better for you than the black camel which you worship besides God."
Some of Zayd's delegation responded positively and accepted Islam while others did not. When Muhammad had finished speaking, Zayd stood up and said:
"O Muhammad, I testify that there is no god but God and that you are the messenger of God."
Muhammad approached him and asked who he was, to which Zayd replied, "I am Zayd al-Khayl the son of Muhalhil."
"From now on you are Zayd al-Khayr ("Zayd the good") instead, not Zayd al-Khayl," said Muhammad.
During this visit in Medina all those who stayed with Zayd became Muslims.
However, there was an epidemic of fever in Medina and Zayd al-Khayr succumbed to it. He attempted to return home despite his illness, hoping to get back to his people so they might become Muslims at his hands. He struggled to overcome the fever but he died before reaching Najd.