In a video posted on the Kavkaz-Tsentr website, often used by Chechen militants, a man calling himself Muhammad says "on my orders an operation was carried out against God's enemies – [chief mufti] Ildus Faizov and [former deputy chief mufti] Valiulla Yakupov in Kazan on July 19."
Muhammad claims to be the "emir of the mujahedin of Tatarstan" in the video.
He warns "God willing we will continue similar attacks against God's enemies."
Muhammad also calls on all imams in Tatarstan to "return to the fundamentals of Shari'a [law]"and, after warning Islamic clerics about dealing with "infidels," says, "in this way you can save yourselves from the mujahedin."
The video, which lasts for one minute and 49 seconds, was posted on YouTube on August 3 by "Marat Khalimov."
Faizov survived a car bombing and Yakupov was gunned down in seemingly related incidents on July 18.
Five people were arrested in connection with the attacks, four of them residents of Tatarstan and one an Uzbek national.
Tatarstan was once a stronghold of Islam, conquered by Ivan the Terrible in the mid-16th century.
Despite being part of Russia since then, Tatarstan has retained its Islamic heritage, albeit in moderate form, and oil deposits there have helped make it one of the more affluent regions of Russia.
The day after the deadly attacks in Kazan, a spokesman for Russia's Investigative Committee, Vladimir Markin, indicated that investigators were looking into two different motives for the attacks -- one religious, the other financial.
"After Faizov was elected Chief Mufti of Tatarstan, he chose a tough stance on organizations professing radical Islamic views in the republic," Markin said. "Faizov was preventing the activities of these organizations that propagate this trend in Islam.
"Besides this, he began supervising the flow of money to [the pilgrimage tour operator] Idel-Hajj, which was sending Muslims to [the Hajj pilgrimage] in Mecca. In connection with this, he had a conflict related to that with the head of that organization, who threatened Faizov."
President Vladimir Putin blamed a lack of "preventive measures" for allowing such an attack to take place. These comments were interpreted by some as heralding a crackdown in Tatarstan.
In the video, the man calling himself Muhammad appears holding a Kalashnikov rifle but it was unclear how many, if any, fighters are under his command and he gives no details about the "mujahedin of Tatarstan," a previously unheard of group.
In a related event, on August 5, Tatarstan's Invesgitative Committee department put two local residents on the wanted list for allegedly helping plan the July attacks on the two Islamic clerics.
The department said Robert Valeyev and Rais Mingaleyev were wanted for serious crimes, including murders and terrorism.
With reporting by IFX Rus., AFP, and Kavkaz-Tsentr