Nimr al-Nimr, who spent more than a decade studying theology in Iran and was a driving force behind anti-government protests in Saudi Arabia in 2011, was put to death along with 46 other men, the Saudi interior ministry said.
Mass executions: Saudi Arabia executes 47 over terror charges
Along with the 56-year-old were Shia activists and Sunnis accused of involvement in Al-Qaeda killings.
The executions sparked protests in at least one city in Saudi Arabia's oil-rich Eastern Province, where Shia complain of marginalisation, as well as in Iran, Iraq and Bahrain.
The strongest condemnation came from Riyadh's longtime rival Tehran.
"The Saudi government supports terrorist movements and extremists, but confronts domestic critics with oppression and execution," Iranian foreign ministry spokesman Hossein Jaber Ansari said.
It will "pay a high price for following these policies", he warned.
Saudi foreign ministry spokesman Mansur al-Turki called Iran's reaction "irresponsible", and Riyadh summoned Tehran's envoy in protest.
Soon after, protesters hurled petrol bombs and stormed the Saudi embassy in Tehran before being cleared out by police, the ISNA news agency reported, adding that flames could be seen rising from the building.
"The fire has destroyed the interior of the embassy," an eyewitness told AFP, speaking on condition of anonymity. "The police are everywhere and have dispersed the demonstrators, some of whom have been arrested."
'Exacerbating sectarian tensions'
Websites carried pictures of demonstrators apparently clutching the Saudi flag, which had been pulled down and protesters had been able to climb up onto the roof of the embassy before they were made to leave, according to ISNA.
In Mashhad, Iran's second biggest city, demonstrators meanwhile set fire to the Saudi consulate, according to news websites, which published photos of the alleged assault.
The incidents came after the United States and European Union expressed alarm over the executions, with Washington warning that Riyadh "risked "exacerbating sectarian tensions at a time when they urgently need to be reduced".
Saudi Arabia reopens embassy in Baghdad
Saudi Arabia's interior ministry said the executed men had been convicted of adopting the radical "takfiri" ideology, joining "terrorist organisations" and implementing various "criminal plots".
An official list published included Sunnis convicted of involvement in Al-Qaeda attacks that killed dozens of people - Saudis and foreigners - in 2003 and 2004.
Among them was Fares al-Shuwail, described by Saudi media as Al-Qaeda's top religious leader in the kingdom.
All those executed were Saudis, except for an Egyptian and a Chadian.
Some were beheaded, while others were shot by firing squad, said the ministry spokesman.
Elsewhere in the region, other Shia countries and groups also reacted angrily.
In Saudi ally Bahrain, police used tear gas to disperse dozens of youths from the majority Shia population protesting against the executions.
In Iraq, hundreds of people demonstrated in the holy Shiite city of Karbala and prominent Shia lawmaker Khalaf Abdelsamad called for the closure of Riyadh's newly-reopened embassy in Baghdad and the expulsion of its ambassador.
Instigator of sedition
Lebanon's Hezbollah, an ally of Tehran, said Saudi Arabia's rulers were "global criminals" and denounced Nimr's execution as a "heinous crime".
And in Yemen, where the kingdom is leading a coalition against Shia rebels, the religious scholars' association controlled by them condemned the execution.
Nimr's brother, Mohammed, said he had hoped that "wisdom and a political solution" would prevail to spare the cleric's life.
He warned that his execution could trigger "negative reactions" inside and outside Saudi Arabia.
The governments of Bahrain and the United Arab Emirates, however, voiced support for Saudi Arabia, saying the executions were necessary to confront extremism.
Executions have soared in the country since King Salman ascended the throne a year ago, with 153 people put to death in 2015, nearly twice as many as in 2014.
Rights groups have repeatedly raised concern about the fairness of trials in Saudi Arabia, where murder, drug trafficking, armed robbery, rape and apostasy are all punishable by death.
Nimr was arrested in 2012, three years after calling for Eastern Province's Shia-populated Qatif and Al-Ihsaa governorates to be separated from Saudi Arabia and united with Bahrain.
The interior ministry had described him at the time of his arrest as an "instigator of sedition".
A video on YouTube in 2012 showed Nimr making a speech celebrating the death of then-interior minister Prince Nayef bin Abdulaziz.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ