After the Conquest of Makkah, the tribes around Makkah and Madina accepted Islam. It was now the turn of the remoter parts of Arabia to be introduced to Islam. The Holy Prophet sent missions to various parts of Arabia. One of such missions under Khalid b Walid was sent to Yemen to invite the Yemenites to Islam. Khalid b Walid was a soldier and a swordsman, but not a scholar or a preacher. He was a late convert to Islam, and in spite of his enthusiasm did not have that depth in the understanding of Islam which could attract others to Islam. The Yemenites were proud of their ancient civilization and culture, and could not believe that anyone from the interior of Arabia, always regarded by them as a backward area, could be a source of enlightenment for them. The Jews and the Christians had their high powered missions in Yemen. Some of the people of Yemen were Christians and some of them were Jews. The Christian priests and the Jewish Rabbis had a strong hold on the people of Yemen and in spite of his best efforts for over six months, Khalid bin Walid was not able to make any headway in Yemen. The Holy Prophet recalled Khalid b Walid from Yemen.