"Vitaly Karayev, this enemy of Allah, was eliminated near his home when he was on his way to the city hall," the Kataib al-Khoul group said in a statement posted on the kavkazcenter site.
The group accused him of "sanctioning the persecution of women in Islamic clothes in public places, which resulted in women being repeatedly insulted and humiliated."
"The execution of this enemy of Allah was carried out by a naib [deputy] of the amir of Kataib al Khoul," the statement said.
The mayor of Vladikavkaz, the capital of Russia's North Caucasus republic of North Ossetia, was killed after leaving for work on Wednesday morning. He was shot while getting into his car outside his home, and was rushed to hospital by his bodyguards.
A hospital official said he died of a bullet wound to the heart.
A police source said the attack was probably carried out by a sniper. "There was a single bullet hole in the door of his vehicle. Presumably it was a single sniper shot which proved fatal," he said.
A senior North Ossetian investigator, Chermen Zangiyev, said the most likely motive for the killing was Karayev's "professional activities."
Karayev, who died at the age of 46, became Vladikavkaz mayor in February after his predecessor quit the post.
North Ossetia was the focus of international attention in September 2004, when terrorists seized Beslan's School No.1 killing 331 people including 186 children. The republic neighbors the troubled Chechnya and Georgia, with which Russia fought a brief war in August.
Add to blog
You may place this material on your blog by copying the link.
Image Galleries: Yury Gagarin: A down-to-earth person
Infographics: The Linguistic Diversity of the Planet
During Vladimir Putin’s annual Q&A session some members of the Valdai International Discussion Club asked him several questions. How united is the West in its desire to punish Russia? Which EU countries are in favour of isolating Russia? Is this even possible? And what is going on in Ukraine?