Protesters have stormed the Saudi Embassy in the Iranian capital, setting fires and throwing papers from the roof.
The unrest in Tehran came after Saudi Arabia executed a leading Shi'ite cleric, Nimr al-Nimr, along with 46 other condemned prisoners.
Nimr was considered a terrorist by Riyadh but hailed in Iran as a champion of the rights of Saudi Arabia's marginalized Shi'ite minority.
Iran's Supreme Leader Aytatollah Ali Khameni said on January 3 that Saudi Arabia faced "divine revenge."
A group of hard-liners have called for further protests on January 3 outside the Saudi Embassy in Tehran.
Iran's hard-line Revolutionary Guards had promised "harsh revenge" against the Saudi Sunni royal dynasty for his execution.
The Iranian Foreign Ministry summoned the Saudi envoy in Tehran to protest Nimr's execution.
Saudi Arabia summoned Iran's envoy to the kingdom to protest critical comments by Iranian authorities.
In Iraq, whose Shi'ite-led government is close to Iran, prominent religious and political figures demanded that ties with Riyadh be severed.
In Washington, a State Department spokesman said Washington was concerned the execution of Nimr could worsen sectarian tensions at a time when they urgently need to be reduced.
Nimr was a central figure in Shi'ite protests that erupted in 2011 as part of the Arab Spring in the Sunni-ruled kingdom's east, where the Shi'ite minority complains of marginalization.
Iran previously warned that executing the cleric would "cost Saudi Arabia dearly."
Ayatollah Ahmad Khatami, a member of the Assembly of Experts and a Friday Prayer leader, denounced the execution as a "crime" by Saudi Arabia's "infamous regime."
"This...blood will stain the collar of the House of Saud and wipe them from the pages of history," Khatami was quoted as saying on January 2.
Iran’s powerful Islamic Revolutionary Guards Corps (IRGC) said in a statement that the Saudi government would pay a "heavy price" for “this shameful act,” which it said was a sign of the “decay” of the Saudi rulers.
“The criminal act of execution of Sheikh Nimr the leader of Shia in Saudi Arabia is part of a Zionist conspiracy to sow discord among the world Muslims which will be aborted by the Heavenly blessings coming down to us by the pure blood of these martyrs,” the statement published by Iranian media said.
The Twitter account of Supreme Leader Khamenei paid tribute to Nimr, calling him a “martyr.”
"Awakening is not suppressible," read the tweet on Khamenei's English-language Twitter account, next to a photograph of Nimr.
Earlier, a small group of seminary students protested the cleric's execution in front of the Saudi Embassy in Tehran on January 2, Iranian domestic media reported. Protesters also rallied outside the Saudi Consulate in Mashhad, where they reportedly brought down a Saudi flag.
Iranian protesters gather outside the Saudi Embassy in Tehran during a demonstration against the execution of prominent Shi'ite Muslim cleric Nimr al-Nimr by Saudi authorities on January 2.
The cleric's execution also prompted angry reactions in other countries in the region, including in Shi'ite-majority Iraq and in Bahrain.
Iraqi Prime Minister Haidar al-Abadi warned that Nimr’s execution would have repercussions on regional security.
He wrote on his verified Facebook account that muffling voices and executing opponents "would lead to nothing but more destruction," expressing "intense shock" upon hearing the news of the execution.
Former Prime Minister Nuri al-Maliki said Nimr's execution would "topple the Saudi regime".
Iraqi lawmaker Muhammad al-Sayhud warned that Nimr's execution was intended to fuel sectarian strife in the region.
"This measure taken by the ruling family [of Saudi Arabia] aims at reigniting the region, provoking sectarian fighting between Sunnis and Shi'a," he told Al-Sumaria TV.
Prominent Iraqi Shi'ite cleric Muqtada al-Sadr called for demonstrations in Persian Gulf countries and in Iraq to protest the execution of Nimr by Saudi Arabia.
"I ask that the Shi'a of Saudi Arabia...show courage in responding even through peaceful demonstrations, and the same for the Shi' in the Gulf, so as to deter injustice and government terrorism in the future," Sadr said on his website.
In Bahrain, police used tear gas against several dozen people protesting Nimr’s execution while carrying his pictures.
Meanwhile, Nimr's brother said the family was shocked by news of the execution but hoped that any reaction would be peaceful:
"We hope that any reactions would be confined to a peaceful framework. No one should have any reaction outside this peaceful framework. Enough bloodshed," Muhammad al-Nimr told Reuters.
He said the cleric was found guilty of seeking "foreign meddling" in the kingdom, "disobeying" the country's rulers, and taking up arms against the security forces.
Nimr’s brother was later quoted as saying that Saudi authorities told the family that the cleric had already been buried without informing them at which cemetery.
Hundreds of members of its Shi'ite minority were arrested after the protests during which several policemen were killed in shooting and firebomb attacks.
The kingdom also detained thousands of militant Islamists after a series of Al-Qaeda attacks from 2003-06 that killed hundreds, and has convicted hundreds of them.
The ministry said the executions were carried out on January 2 in 12 different areas of the kingdom.
The executions are Saudi Arabia's first in 2016. At least 157 people were put to death last year, a big increase from the 90 people killed in 2014.
With reporting by Reuters, dpa, AFP, AP, the BBC, Fars and Mehr