Gazprom chief Alexei Miller said that as of 0700 GMT Ukraine's Naftogaz had used up all the gas it had paid for and "no new upfront payment has been made".
"As such, deliveries have been stopped until the receipt of new payments from the Ukrainian company," Miller said in a statement.
"The refusal to buy Russian gas will create serious risks for the reliable transit of gas to Europe through Ukraine and for the supply of gas to Ukrainian consumers during the upcoming winter," Miller warned.
Moscow turned the taps back on in October under a deal that saw Kiev switch to a pre-payment system, meaning that cash-strapped Ukraine must stump up money in advance to cover Russian gas deliveries.
Also Read
Some 15 per cent of the gas used in Europe travels through Ukraine, and the EU has been involved in mediating the dispute between the two sides.
Gazprom's announcement comes as tensions between Moscow and Kiev have risen again over the annexed Crimea peninsula after explosions in Ukraine cut electricity supplies to most of the territory and Kiev ordered a halt to goods deliveries.