The sharp and pungent proclamation read out by the Commander of the Faithful during Haj season of the ninth year of migration at Mina, on behalf of the Prophet, and official declaration by him to the effect that Allah and His Prophet were disgusted with the idolaters and they (the idolaters) should decide once and for all within a period of four months, either to embrace Islam and forsake idol-worship or to get ready for total war, had a very deep and quick effect. The tribes of different regions of Arabia, which had so far declined to submit to the logic of the Qur'an, and the law of Allah, on account of enmity and grudge, and insisted on sticking to their evil and indecent habits, superstitions, foolish beliefs, and worship of stones and clay, became helpless now and sent their representatives to the headquarters of Islam (Madina). Everyone of these deputations had discussions and conversation with the Prophet. Ibn Sa'd in his Tabaqat-i Kubra has recorded the particulars of seventy-two persons out of them. Arrival of these deputations in large numbers and that too after declaring the proclamation, shows that in the beginning of the tenth year of migration no dependable fort had been left for the polytheists of Arabia, otherwise they would have taken refuge there and waged war with the help of one another.
The period of four months had not yet passed when the entire Hijaz came under the banner of Islam and not a single idol-temple or idol or idolater was left in it, so much so that a number of persons belonging to Yemen, Bahrain and Yamamah also embraced Islam.
PLOT TO KILL THE PROPHET
The chiefs of the tribe of Bani 'Amir were widely known amongst the Arab tribes for their obstinacy and mischief. Three persons from amongst their chiefs named 'Amir, Arbad and Jabbar decided to arrive in Madina at the head of a deputation and somehow to kill the Prophet while having discussions with him in a meeting. Their scheme was that 'Amir should engage himself in discussion with the Prophet and while their conversation was in full swing Arbad should attack the Prophet with his sword and kill him.
Other members of the deputation, who were unaware of this plot of the three persons, declared their fidelity for Islam and the Prophet. However, 'Amir refrained from expressing any inclination towards Islam and said to the Prophet repeatedly, "I want to talk to you in seclusion". Every time he uttered this sentence he looked towards Arbad. However, although he looked at his face very intently he found him calm and tranquil. The Prophet said to him in reply: "Unless you embrace Islam this thing is not possible, (i.e. to see you alone)". At last 'Amir lost all hope of Arbad's assistance in the success of their plot. It would appear that as and when Arbad intended to put his hand on his sword he was stricken with terror and the Prophet's greatness kept him (Arbad) from carrying out his plan. When the meeting ended 'Amir stood up from his place, declared his enmity for the Prophet and said: "I will fill Madina with horses and soldiers to do harm to you". On account of the great forbearance which he possessed, however, the Prophet did not give him any reply, but prayed to Allah to keep him safe from the mischief of the two men. The supplication of the Prophet was accepted soon. 'Amir had an attack of plague while he was on his way, and died in a very bad condition in the house of a woman belonging to the tribe of Bani Salul. As regards Arbad, he was struck by lightning in the desert and was burnt to death. And the fate met by these persons, who had plotted against the Prophet further intensified the people's faith (in Islam).
THE COMMANDER OF THE FAITHFUL
Acceptance of Islam by the people of the Hijaz and the security which the Prophet felt from the side of the Arab tribes enabled him to extend the influence of Islam to the neighbouring areas of Hijaz. For the first time, therefore, he deputed one of his wise companions named Mu'az bin Jabal to Yemen so that he might explain Islam to the people of that region.
While giving him detailed instructions the Prophet also said to Mu'az: "Avoid harsh treatment with the people, and inform them of Divine blessings which are meant for the true believers. When you face the people of the Scriptures in Yemen, and they enquire from you about the key to Paradise, you should tell them that it is the acknowledgment of the Oneness and Uniqueness of Allah"
It would appear that with all his knowledge of the Book and the Sunnah Mu'az did not give a satisfactory reply when he was asked about the rights of a husband over his wife. The Prophet, therefore, decided to send his distinguished disciple Ali to Yemen so that Islam might spread there under his continuous teachings, logical arguments, the strength of his hands, and his unparalleled bravery and moral heroism.
Furthermore, Khalid bin Walid had also been dispatched by the Prophet to Yemen sometime earlier than Ali so that he might remove the obstacles in the way of advancement of Islam, in that area. He did not, however, do anything in this behalf during that period. The Prophet, therefore, called Ali and said to him: "O Ali! I am sending you to Yemen so that you may invite its inhabitants to Islam and inform them about the Command of Allah as well as about the things, which are lawful, and which are unlawful. At the time of your return to Madina you should collect zakat from the people of Najran as well as the taxes which they are liable to pay and should deposit the same in the public treasury.
Ali replied to the Prophet most respectfully in these words: "I am a young man and have never arbitrated throughout my life and have never occupied the seat of justice". The Prophet placed his hand on Ali's chest and prayed for him in these words: "O Allah! Guide the heart of Ali and protect his tongue from errors". Then he said: "O Ali! Do not quarrel with anyone and try to guide the people to the right path with logic and good behaviour. By Allah! If Allah guides someone to the right path through you, it is much better than that on which the sun shines".
In the end the Prophet made four recommendations to Ali:
During his stay in Yemen, Ali passed spellbound judgements, most of which are recorded in the books of history.
The Prophet did not content himself with guidance but he also wrote a letter to the people of Yemen inviting them to Islam, gave it to Ali and directed him to read it over to them.
Bara' bin 'Azib was Ali's attendant in Yemen. He says that when Ali reached the border of Yemen, he arranged the ranks of the Muslim soldiers who were already stationed there under the command of Khalid bin Walid and offered the morning prayers in congregation. Then he invited the tribe of Hamdan, which was one of the biggest tribes of Yemen, to hear the message of the Prophet. First he praised Allah. Then he read out the Prophet's message to them. The grandeur of the meeting, the sweetness of the narration and the greatness of the words of the Prophet impressed the people of Hamdan tribe so much that they embraced Islam within a day. Imam Ali wrote a letter to the Prophet informing him of the developments. The Prophet was greatly pleased to learn the good news. He thanked Allah and said: "May the tribe of Hamdan be blessed".
The conversion of Hamdan tribe to Islam became the cause of other people of Yemen embracing Islam gradually.
 Tabaqat-i Kubra, vol. II, pp. 230 - 291.
 Seerah-i Ibn Hisham, vol. II, pp. 568 - 569.
 Seerah-i Ibn Hisham, vol. II, page 590.
 Sahih Bukhari, vol. V, page 163.
 Tarikh-i Kamil, vol. II, page 305; Biharul Anwar, vol. XXI, pp. 360 - 363.