Kuzmin, who is facing charges of abuse of office in Russia that he says are politically motivated, was arrested Sunday at Vienna's Schwechat Airport, Austrian prosecutors said.
"He was traveling under his real name and cooperated fully with authorities," regional prosecutor Friedrich Koehl said by telephone from Kroneuburg, Austria.
Austrian police were acting on an international arrest warrant for Kuzmin based on the ruling of a Stavropol court, Koehl said.
A Kroneuburg court ordered Kuzmin to remain in custody for two weeks, after which he could be released on bail, Koehl said.
The Investigative Committee said in a statement Tuesday that it that it was preparing an extradition request for Austrian authorities.
Kuzmin has been charged on two counts of abuse of office, including the embezzlement of 19 million rubles ($807,000), as well as one count of libel, committee spokesman Vladimir Markin said in the statement. If convicted, he faces up to 10 years in prison.
The criminal case against Kuzmin, which unfolded ahead of the State Duma elections last December, has been called a smear campaign against a leader who had become too serious a threat to the pro-Kremlin party United Russia, whose election ticket was led by then-President Vladimir Putin.
In March 2007, Kuzmin led A Just Russia, a center-left, pro-Kremlin party created in 2006, to a rare victory in regional parliamentary elections over United Russia and the political machine of United Russia and Alexander Chernogorov, then the governor of Stavropol.
In November, just weeks before the Duma elections, Kuzmin was removed from A Just Russia's ticket over purported campaign violations.
In a bizarre turn, a senior local police official announced during a televised news conference that Nazi flags and medals had been found during a search of Kuzmin's office. The Nazi regalia were shown repeatedly on local television in the run-up to the elections.
Prosecutors say Kuzmin exceeded his authority by giving city-owned real estate to his associates and illegally leasing an armored BMW sports utility vehicle. They also accused Kuzmin of slandering Chernogorov.
A Stavropol court later stripped the mayor of his office and ordered his arrest in absentia.
Kuzmin had left the country well before the Dec. 2 Duma elections, Kommersant reported Tuesday.
"He left the country with a Schengen visa last November, flew to Strasbourg and freely moved around European countries," said Sergei Solodovnikov, the Interior Ministry's representative in the Southern Federal District, Kommersant reported.
Kuzmin was detained before boarding a flight from Vienna to another European country, Solodovnikov said.
Koehl, the Austrian prosecutor, said extradition proceedings could take up to a month. Austria and Russia have both ratified a European extradition convention.
Koehl said he could not comment on whether Kuzmin could apply for political asylum because such applications are not handled by the Austrian judiciary.
A Just Russia members have accused authorities of pursuing criminal charges against Kuzmin to prevent a repeat of the party's success in the March 2007 regional elections.
United Russia captured 62 percent in the region in the Duma elections, while A Just Russia garnered just 13 percent.
The investigation has also ensnared Andrei Utkin, the former speaker of the Stavropol regional legislature and a close ally of Kuzmin's.
Utkin was convicted of exceeding his authority by misusing city funds and given a two-year suspended sentence.
A Message from The Moscow Times:
Dear readers,
We are facing unprecedented challenges. Russia's Prosecutor General's Office has designated The Moscow Times as an "undesirable" organization, criminalizing our work and putting our staff at risk of prosecution. This follows our earlier unjust labeling as a "foreign agent."
These actions are direct attempts to silence independent journalism in Russia. The authorities claim our work "discredits the decisions of the Russian leadership." We see things differently: we strive to provide accurate, unbiased reporting on Russia.
We, the journalists of The Moscow Times, refuse to be silenced. But to continue our work, we need your help.
Your support, no matter how small, makes a world of difference. If you can, please support us monthly starting from just $2. It's quick to set up, and every contribution makes a significant impact.
By supporting The Moscow Times, you're defending open, independent journalism in the face of repression. Thank you for standing with us.
Remind me later.