The hardline daily Kayhan called Bruni a prostitute whose lifestyle meant she deserved a similar fate as the Iranian woman who was sentenced to death for adultery.
Carla Bruni was one of several French celebrities who published open letters to Sakineh Mohammadi Ashtiani, whose case has caused international outrage and highlighted Iran's use of stoning as capital punishment.
The wife of President Nicolas Sarkozy wrote: Spill your blood, deprive your children of their mother? Why? because you have lived, because you have loved, because you are a woman, an Iranian? Every part of me refuses to accept this.
Kayhan, whose editor-in-chief is appointed by Supreme Leader Ayatollah Ali Khamenei, reported Bruni's letter on Saturday under the headline: French prostitutes enter human rights uproar.
On Tuesday it returned to the subject, criticising Bruni's illicit relationships with various people and blaming her for causing Sarkozy's divorce from his second wife.
Studying Carla Bruni's record clearly shows the reason why this immoral woman is backing an Iranian woman who has been condemned to death for committing adultery and being accomplice in her husband's murder and, in fact, she herself deserves to die, Kayhan said.
French Foreign ministry spokesman Bernard Valero said the comments by Kayhan were unacceptable and that Paris had passed on its message to Tehran.
At his weekly news conference, Iranian Foreign Ministry spokesman Ramin Mehmanparast called on Iran's media to use more temperate language.
Insulting the officials of other countries and using inappropriate words, this is not approved of by the Islamic Republic of Iran, he said when asked about the issue.
The policies, the manners and the comments of other countries' officials, we criticise them, we make objections to them and we call for them to review their deeds, but we don't think using inappropriate words and insulting words is the right thing to do.
Ashtiani, a mother of two, has received 99 lashes for having an illicit relationship with two men. The stoning sentence has been suspended pending a judicial review but could still be carried out, an Iranian judiciary official has said.
Murder, adultery, rape, armed robbery, apostasy and drug trafficking are all punishable by death under Iran's sharia law, enforced since the 1979 Islamic Revolution. Iran is second only to China in the number of people it executes, according to Amnesty International.
Brazil's President Luiz Inacio Lula da Silva, who has developed close ties with his Iranian counterpart Mahmoud Ahmadinejad, has offered asylum to Mohammadi Ashtiani, prompting an embarrassing public rejection of his offer by Iran.
(Reporting by Ramin Mostafavi in Tehran and Vicky Buffery and John Irish in Paris; Writing by Robin Pomeroy; Editing by Jon Hemming)