Did Muhammad order the murder of eight men for apostasy?
In fact, the eight men from ‘Ukil were not killed for apostatizing, but were held accountable for committing a vicious murder and treason.
We cite this event in full below. But first, reiterate the heinousness Islam attributes to murder. As already mentioned, murder and treason are the only two crimes for which the Qur’an allows the death penalty.
On account of this, We prescribed for the children of Isra’il that whosoever killed a person—unless it be for killing a person or for creating disorder in the land—it shall be as if he had killed all mankind; and whoso gave life to one, it shall be as if he had given life to all mankind. And Our Messengers came to them with clear Signs, yet even after that, many of them commit excesses in the land. 
Here, the Qur’an equates the murder of one person to that of all mankind, demonstrating the high sanctity of life placed on every individual regardless of any differentiating factor. Likewise, the reward for saving one is that of having saved all mankind, demonstrating Islam’s immense emphasis on protecting life. Having set this precedent, the Qur’an issues a warning to those who would dare “kill all mankind” in the subsequent verse 5:34:
The reward of those who wage war against Allah and His Messenger and strive to create disorder in the land is only this that they be slain or crucified or their hands and their feet be cut off on alternate sides, or they be expelled from the land. That shall be a disgrace for them in this world, and in the Hereafter they shall have a great punishment. 
Islam believes in neither absolute punishment nor absolute forgiveness, but in reform. Islamic punishments serve two purposes—to be reformative or to be deterrent. When someone commits an act for which forgiveness will likely reform him or her, forgiveness is employed. Likewise, when someone commits a heinous crime for which reform is no longer possible—such as murder—or the likes of which leniency will fail to deter others from committing the same heinous act, Islam prescribes an exemplary punishment to deter future offenders. Such is the case here.
In 5:33, the Qur’an establishes the heinousness of murder, equating it to killing all mankind. Indeed, the pain an entire society suffers in response to the murder of even one individual ripples far beyond the murder victim. Thus, to ensure murder remains an isolated occurrence, Islam prescribes an aggressive deterrence to would be murderers.
The logic for this is simple. The burden on person A to notmurder person B is extremely low. The harm caused to person B and all those who know person B, should person B be murdered is extremely high. An extremely low burden not to murder combined with an extremely high level of pain and suffering should the murder occur requires even higher consequence to would be murderers. This strategy ultimately serves to mitigate the number of murders.
Keeping this in mind, the Qur’an still reverts to its dominant position on crime and punishment in the next verse—forgiveness. The Qur’an declares in 5:35, “Except those who repent before you have them in your power. So know that Allah is Most Forgiving, Merciful.”  Thus, even those who commit the heinous act of murder may be forgiven if they repent and submit to the government’s authority—as in example, by stopping violence and turning themselves in. In other words, despite murdering “all mankind,” Islam does not prohibit forgiveness altogether, but allows that flexibility should some possibility of reform exist.
With this important background, we now turn to the event in question. The report in Bukhari demonstrates that the eight men from ‘Ukil were not executed due to apostatizing. Instead, they committed murder, theft, treason, did not avail themselves of repentance, and were thus held accountable for their criminal actions. They joined the “Muslim state.” Their apostasy had nothing to do with the punishment they incurred. Anas bin Malik narrates:
A group of eight men from the tribe of ‘Ukil came to the Prophet and then they found the climate of Medina unsuitable for them. So they said, ‘O Allah’s Apostle! Provide us with some milk.’ Allah’s Apostle said. ‘I recommend that you should join the herd of camels.’ So they went and drank the urine and the milk of the camels (as a medicine) till they became healthy and fat. Then they killed the shepherd and drove away the camels. And they became unbelievers after they were Muslims. When the Prophet was informed by a shouter for help, he sent some men in their pursuit. And before the sun rose high, they were brought. And he had their hands and feet cut off. Then he ordered for nails which were heated and passed over their eyes. And whey were left in the Harra (i.e. rocky land in Medina). They asked for water. And nobody provided them with water till they died (Abu Qilaba. a sub-narrator said. ‘They committed murder and theft and fought against Allah and His Apostle and spread evil in the land.’) 
Compare the account of men who simply left Islam with those who sought protection and help under the Medina state, were given whatever they asked, then murdered their caretaker, stole his property, began to spread violence in the land, and did not repent for their actions. At a time when the Medina state itself was subject to attack from all sides, such punishments were necessary to ensure protection of the Muslim state as whole—Jewish and Muslim tribes alike.
Indeed, Prophet Muhammad loathed to harm anyone and inclined to forgiveness as often as possible. He even forgave the man who caused his daughter to fall from a camel, have a miscarriage, and later also die from injuries sustained in the fall. But this incident threatened the entire state. It would be unjust to risk the safety of the entire state of Medina by not delivering the pre-ordained punishment for those who commit murder and treason.
Consider the following well-known incident from Bukhari:
Narrated Salim’s father: “The Prophet sent Khalid bin Al-Walid to the tribe of Jadhima and Khalid invited them to Islam but they could not express themselves by saying, ‘Aslamna (that is, we have submitted),’ but they started saying ‘Saba’na! Saba’na (that is, we have come out of one religion to another).’ Khalid kept on killing (some of) them and taking (some of) them as captives and gave every one of us his captive. When there came the day then Khalid ordered that each man (that is, Muslim soldier) should kill his captive, I said, ‘By Allah, I will not kill my captive, and none of my companions will kill his captive.’ When we reached the Prophet, we mentioned to him the whole story. On that, the Prophet raised both his hands and said twice, ‘O Allah! I am free (or innocent or not responsible for) from what Khalid has done.’ 
Here, two opposing ideologies are presented—one of harshness and one of compassion. Prophet Muhammad clearly chose compassion and condemned harshness. Compassion was his nature. Taking these accounts into consideration, it is clear from a historical perspective the fate of the men from ‘Ukil was not based on those men apostatizing, but on the protection of the state of Medina. These men committed violence, theft, murder, and treason, and were thus held accountable for their own actions.
 Qur’an 5:33.
 Qur’an 5:34.
 Qur’an 5:35.
 Bukhari, Vol. 4, Book 52, #261.
 Bukhari, Vol. 5, Book 59, #628.