Khalid bin Walid was born around 584 in Mecca to the chief of the Bani Makhzum clan of the Quraish Tribe. His clan was responsible for warfare, and his father was well off. These two factors combined to make him proficient in warfare and fighting.
As an adult, Khalid had grown to become a strong man and was well known among the Quraish for his fighting abilities. Following Muhammad's proclimation of the new faith of Islam, many battles were fought between the new Muslims and the Quraishi tribes. Khalid's military genius was responsible for turning the Battle of Uhud into a victory for the Quraishi forces after what had looked like a sure defeat. Following the Truce of Hudaibiya, Khalid became a Muslim. He was impressed by the steadfastness and fearlessness of the Muslims, something he had seen first hand. Upon accepting the religion, he went to Muhammad personally and apologized for his previous actions, and asked Muhammad to pray to God to forgive Khalid. Khalid also vowed to raise his sword in the path of Islam, rather than fighting against it. Despite the initial mistrust of some Muslims, Khalid won the trust of his new comrades and became a commander of Muslim armies.
During the caliphate of Abu Bakr, Khalid was responsible for putting down the rebellion led by the imposter Mosailima at the Battle of Akraba. And later he took Iraq from the Persian Empire in one campaign. During the reign of Umar ibn al-Khattab, Khalid led the Muslim armies in Syria against the Byzantine Empire. Under his leadership, Damascus was captured by the Muslim armies. At the Battle of Yarmuk, all of Syria was taken from the Byzantines.
Following this battle, Khalid was extremely popular. This worried the caliph Umar who did not want the popularity of his general to interfere with people's beliefs in God, so he recalled Khalid and removed him of his commander status. Despite Khalid's desire to continue leading his armies, he obliged. Rather than stay in Medina though, he returned to the field of battle as a regular soldier and fought admirably.