Shahla Jahed, 40, was hanged in Tehran for stabbing to death the wife of 1980s football star Nasser Mohammadkhani, the woman's lawyer told Irna news agency.
Mr Mohammadkhani, who had been in a so-called temporary marriage with Jahed, reportedly attended the execution.
International human rights groups had campaigned for her release since she was jailed more than eight years ago.
The Council of Europe said the execution showed that Iran's government had "little respect for human rights".
"I am dismayed by this latest execution in Iran and also by the inhumane way in which it was carried out," said the organisation's secretary-general Thorbjorn Jagland.
The execution is the 146th in Iran this year, according to AFP news agency.
The Irna news agency reported that Jahed prayed prior to the hanging, and then burst into tears and shouted for her life to be spared.
The victim's brother was at the execution and pulled the chair from under her, according to reports.
Final pleas
Jahed had been living with Mr Mohammadkhani, an international footballer who played in the late 1980s, in a temporary marriage - a practice known as sigheh which is allowed under Shia Islam.
She first confessed to the murder of Laleh Saharkhizan, but later retracted the statement in court.
Mr Mohammadkhani was initially suspected of complicity in the murder and jailed for several months, but he was released after Jahed's confession.
The fact that she was his temporary wife allowed him to avoid being charged with adultery, although he was sentenced to 74 lashes for drug-taking after the court heard he had smoked opium with Jahed.Before the execution, Jahed's sister made a final plea to Ms Saharkhizan's family to ask for the sentence not to be carried out.
"Firstly I have to say that we would like to extend our apologies to Laleh's family for Shahla turning up in her marital life in the first place," Jahed's sister, who did not want to be named, told BBC Persian.
"Secondly we are still shocked by what Shahla has done and we're still in disbelief."
Malcolm Smart, Amnesty director for the Middle East and North Africa, said there were "strong grounds" to believe she had not receive a fair trial.
"She may have been coerced into making a 'confession' during months of detention in solitary confinement," he said in a statement.
"She retracted that confession at her trial but the court chose to accept it as evidence against her."
The initial verdict was overturned in 2008 after the judiciary cited "procedural flaws", but Jahed was again sentenced to death in February 2009.
Iran has attracted international criticism over the separate case of Sakineh Mohammadi Ashtiani, an Iranian woman who was sentenced to death by stoning for adultery.
After campaigns for her release around the world, her stoning sentence was suspended, although she could still be hanged for murder.
BBC News - Iran hangs footballer's mistress Shahla Jahed
Whether the punishment is prison, death, or a fine, the notion that someone should not be punished, because they either refused to confess to the crime or they retracted their confession... is absurd. I understand that for those who see the death penalty as inhumane this is shocking... however to be imprisoned for life while refusing to admit you murdered someone is no different than being executed while refusing to admit you are guilty. Either way their is always the risk that someone will be punished for something they did not do.
That is a chance we have to take unless we want to live in a society where we only face consequences for the things we are willing to admit to. How long does anyone think a society like that would last before it devolved to the point that no one was ever safe anywhere the only people punished for crime are those stupid enough to admit they did it?
Although I do not agree with Iran's system of multiple permanent and temp wives... I have no problem with a government exacting punishment against those who have been found guilty of crimes... even if the convicted refuse to confess.