Ali was sent in December with 300 well armed horsemen, to attack the Banu Nakha and reduce them to submission. This was the first army Muhammad sent forth to conquer Yemen, Ali was met with little opposition, when he attacked the inhabitants, he caused severe and extensive damage all around Yemen. Ali returned with many kinds of War spoils, which included women, children, camels and flock. The people of Yemen that were attacked by Ali were driven to despair and joined together as a group to attack him. They fired arrows and stones at him, the Muslims then charged at them and killed 20 people. William Muir described it as a "slaughter". Ali held back the army from pursuing the enemy, so he could call on them one more time to accept his terms. The tribe did this quickly and submitted themselves to Muadz, Muhammad's envoy in Yemen.
The event is mentioned by the Muslim jurist Tabari, he wrote:
The Messenger of God dispatched Ali b. Abi Talib with an army to the Yemen in Ramadan [Tabari, Last Years of the Prophet, Pg 89].
The event is also mentioned in the Sunni hadith collection Sahih al-Bukhari (in book 59, Military Expeditions), it mentions what Muhammad instructed Muadz to do:
(Allah's Apostle said to Muadh when he sent him to Yemen, "You will go to the people of the Scripture. So, when you reach there, invite them to testify that none has the right to be worshipped but Allah, and that Muhammad is His Apostle. And if they obey you in that, tell them that Allah has enjoined on them five prayers in each day and night. And if they obey you in that tell them that Allah has made it obligatory on them to pay the Zakat which will be taken from the rich among them and given to the poor among them. If they obey you in that, then avoid taking the best of their possessions, and be afraid of the curse of an oppressed person because there is no screen between his invocation and Allah."Sahih al-Bukhari, 2:24:573