Gazprom accuses Ukraine of an "unprecedented" shutdown of transit pipelines. It says only 40m cubic metres of gas is getting through to Europe, instead of 225m cu m.
Serbia's Srbijagas, which imports 92% of its natural gas from Russia, said it had about 10 days' of gas left, Reuters reported.
Slovakia says it will declare a state of emergency over the drop in gas supplies, though it aims to prevent the shortage hurting key public services and ordinary consumers.
The Austrian energy company OMV said it would now have to tap into its gas reserves after its supply fell to 10% of the expected level.
Bulgaria, almost wholly dependent on Russian gas via Ukraine, says it has sufficient supplies for just a few days. It says no more gas is flowing through a pipeline that also supplies Turkey, Macedonia and Greece.
Bulgarian President Georgi Purvanov said the situation was grounds for restarting a nuclear reactor, shut as part of Bulgaria's accession to the EU in 2007.
Gazprom decided to cut exports through Ukrainian pipelines by a fifth in a row over unpaid bills.
Early on Tuesday, Ukraine's Naftogaz said Russia had cut gas transit supplies by more than two-thirds and listed nine countries, including Germany, Poland, and Hungary which would receive reduced supplies as a result.
Gazprom's Alexander Medvedev said gas flow through Ukraine was a fraction of its usual level
"Naftogaz of Ukraine considers that in such a case if European users receive less volumes of natural gas, all claims of the noted countries must be directed to Gazprom," said a statement on the company's website.
Russian gas supplies to Turkey via Ukraine have been completely cut, the Turkish government said.
The Turkish government announced it was increasing the flow through an alternative pipeline, under the Black Sea, to compensate.
Turkey gets about 65% of its gas from Russia and about one-third of its daily supply has now been cut, the BBC's Sarah Rainsford reports. But the government says it has sufficient gas stocks to avoid immediate economic hardship.
Czech supplies also fell significantly overnight, and Croatia, which imports 40% of its gas, said supply of Russian gas via Ukraine had completely halted.
EU deplores quarrel
In a statement on Tuesday, a European Commission spokesman said that "without prior warning and in clear contradiction with the reassurances given by the highest Russian and Ukrainian authorities to the European Union, gas supplies to some EU member states have been substantially cut - this situation is completely unacceptable".
"The Czech EU presidency and the European Commission demand that gas supplies be restored immediately to the EU and that the two parties resume negotiations at once with a view to a definitive settlement of their bilateral commercial dispute."
The new EU member states in Central and Eastern Europe are heavily - and in some cases entirely - dependent on Russian gas imports. Yet Germany and Italy together account for nearly half of the Russian gas consumed in the EU.
German Economy Minister Michael Glos called on Russia and Ukraine to resume talks, and is due to hold talks with senior Gazprom officials later on Tuesday.
But he said Germany could cope with any shortages. "Gas storage sites are full. And Germany gets its gas from different sources, for example from Norway or the Netherlands. Supplies from there could be increased," he said.
Many other countries are now tapping strategic reserves, built up to cope with just such a development, says the BBC's Europe correspondent Nick Thorpe.
Gazprom has promised to pump extra supplies through other pipelines - the Yamal from Arctic Russia through Belarus to Germany, and the Blue Stream to Turkey under the Black Sea.
The move to reduce supplies going through the Ukraine by a fifth came after Russian Prime Minister Vladimir Putin held talks with Gazprom CEO Alexei Miller.
Mr Miller recommended that deliveries via Ukraine should be reduced "by the amount stolen by Ukraine, that is 65.3 million cubic metres of gas".
Ukraine has denied stealing gas, saying technical problems are disrupting the onward flow of gas to Europe.
The row between Russia and Ukraine has been simmering for weeks. Gazprom says Ukraine owes it more than $600m (£413m); Ukraine says it has paid its debt. The two sides have also failed to agree on the price Ukraine should pay for gas in 2009.
A similar row between Gazprom and Ukraine at the beginning of 2006 led to gas shortages in several EU countries.
EU officials have been meeting in Brussels to discuss the dispute and a delegation has also been sent for talks with both Ukrainian and Gazprom officials.
Gazprom wants Ukraine to pay $450 per 1,000 cu m of gas - more than double what Kiev says it is willing to pay, yet still less than what most EU states pay.
Have you been affected? Are you worried by the crisis?
Send your comments using the post form below.
In most cases a selection of your comments will be published, displaying your name and location unless you state otherwise in the box below.
The BBC may edit your comments and not all emails will be published. Your comments may be published on any BBC media worldwide.
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.