The meeting between Gazprom's Alexei Miller and Naftogaz's Oleh Dubina was their first since negotiations broke down on New Year's Eve over prices for 2009 and Ukraine's debt.
The talks were unexpected because the two men flew to Brussels from Moscow on Thursday to meet with EU officials. A Naftogaz spokesman said Dubina and Miller could return to the Russian capital to continue talks.
"So far no compromise has been reached," spokesman Valentyn Zemlyansky said.
Gazprom stopped all gas shipments to Ukraine on Jan. 1 but kept supplies flowing to Europe through Ukraine's pipelines until Wednesday, when all deliveries stopped.
The cutoff has left more than a dozen countries struggling to cope in the depths of winter. Factories shut down in eastern Europe, schools closed and tens of thousands of people scrambled to find other ways of keeping warm.
EU Commission President Jose Manuel Barroso has pressed the prime ministers of Russia and Ukraine for a quick resolution to the standoff.
"If this matter is not solved, it will raise very serious doubts about the reliability of Russia as a supplier of gas to Europe and Ukraine as a transit country," he said Wednesday.
Europe depends on Russia for one-quarter of its natural gas, and about 80 percent of that is shipped through pipelines crossing Ukraine. Other smaller pipelines run through Belarus and Turkey.
Austria, Bulgaria, Croatia, the Czech Republic, France, Greece, Hungary, Italy, Macedonia, Romania, Serbia, Slovakia, Slovenia and Turkey all reported a halt in Russian gas shipments by Wednesday. Germany and Poland reported substantial drops in supplies.
Barroso said Ukraine and Russia both agreed to accept international monitors that could verify the flow of gas, a concession from Ukraine that would meet one of Russia's conditions for resuming gas supplies. Russia has accused Ukraine of siphoning off gas meant for European customers.
Russia is also demanding that Ukraine pay significantly more for its gas. Last year, Russia charged Ukraine $179.50 per 1,000 cubic meters, about half what it charged its European customers.
Russia's last offer before talks broke down was $250, but President Dmitry Medvedev said late Wednesday that Moscow would now insist that Kiev pay European prices "without a discount."
Naftogaz deputy chief Volodymyr Trikolich said Thursday his company continues to insist on a price of $201 per 1,000 cubic meters and wants to raise the transit fee from $1.7 to $2 per 100 kilometers of transit.
Medvedev also demanded full payment of Ukraine's $600 million debt to Gazprom, which Ukraine has said it will not pay until the issue is settled in arbitration courts.
Czech Deputy Foreign Minister Alexandr Vondra, whose country holds the EU presidency, ruled out the possibility of EU countries paying any of Ukraine's debt.
"I don't think that is what we need to do," Vondra told reporters at an EU foreign ministers' meeting Thursday in Prague.
Ukraine, which has a vast underground storage system full of natural gas, says it can weather the dispute until early April. However, the Ukrainian capital, like many areas in Eastern Europe and the Balkans, has already experienced heating problems with residents being forced to bundle in winter clothes and turn on electric heaters to keep warm.
Gazprom, meanwhile, is losing substantial income during a peak season for gas consumption. It also will soon see an excess of gas in its system, which will create storage and other problems.
France's Prime Minister Francois Fillon said in a statement late Wednesday that the suspension of Russian gas supplies was "totally unacceptable." He urged the EU to press Russia to respect its engagements on supplies to Europe and to press Ukraine to guarantee the transit of gas across its territory.