After an initial probe into the Beslan school carnage, Moscow has pointed at the involvement of Basayev and Maskhadov in the bloodiest terror attack in Russia, which left more than 300 dead, many of them schoolchildren.
"In the course of a number of years the leaders of band-formations Shamil Basayev and Aslan Maskhadov have committed inhuman terrorist acts on the territory of the Russian Federation resulting in irreplenishable losses," a Federalnaya Sluzhba Bezopastnosti - FSB release said while offering the reward and guaranteeing anonymity and protection.
The FSB will pay the reward "for reliable information on their whereabouts leading to the neutralisation of these people."
News of the reward broke as state television was broadcasting footage of Prosecutor General Vladimir Ustinov briefing President Vladimir Putin on the investigation into the taking of more than 1,200 hostages in a school in southern Russia last week.
Ustinov said 326 hostages had been killed and 727 wounded in the attack which ended Friday following explosions and gunfire as hostages tried to flee and special forces tried to help them.
He said 210 bodies had been identified and forensic workers were trying to identify 32 body fragments. The death toll could rise, Ustinov added.
Russian Foreign Ministry had earlier today said it would seek the extradition of Chechen leaders allegedly involved in terrorism from the safe haven enjoyed by them in the US and UK.
In a reference to Chechen separatist leader Aslan Maskhadov's emissaries Ilyas Akhmadov and Akhmad Zakayev, who have been granted political asylum in the US and UK respectively, a Russian Foreign
"Already the first results of the investigation of the terrorist act in Beslan indicate the involvement of Maskhadov and his accomplices in it," a foreign ministry statement said.
It said that "not merely bandits", but international terrorists are waging a war in the North Caucasus against Russia and must not escape the most severe punishment under the law, even if they are hiding outside the Russian Federation.
"There should be no double standards" the Russian Foreign Ministry said underscoring that it was high time for the West to give up its biased attitude towards Russia.
"We cannot put pressure on judges anywhere, nor do we intend to. Our actions will be carried out strictly within international law and legal rules. Terrorists and their accomplices must appear before a Russian court and face punishment for their crimes," the statement said.
Moscow intends to take a number of "appropriate extra steps", including in contact with its foreign partners for extradition of Akhmadov and Zakayev.
The Foreign Ministry statement came in the wake of President Vladimir Putin accusation of the US of undermining Russia's struggle against terror by meeting with Chechen separatists.
Putin told a group of Western policy analysts late on Monday night that his administration has repeatedly complained about meetings between US officials and representatives of Chechen separatists, but to no avail.
"Washington has invariably responded with "we will get back to you" or "we reserve the right to talk with anyone we want," Putin told a group of Western journalists and academics during a wide-ranging policy discussion, 'Moscow Times' said. This approach reflects a Cold War mentality among some US politicians, he said.
"Why don't you meet Osama bin Laden, invite him to Brussels or to the White House and engage in talks, ask him what he wants and give it to him so he leaves you in peace? Why don't you do that?" Putin told participants at the annual Valdai Forum.