"The Russian-Ukrainian gas dispute has prompted a search for long-term solutions to energy supplies on the basis of international standards," Miroslav Kostelka told a news conference with European Commission Moscow office chief Marc Franco.
Franco said the European Union could lose confidence in Russia and Ukraine as economic and political partners.
The statements came as Moscow and Kiev reached a deadlock in attempts to resume Russia's Europe-bound gas supplies via Ukraine, which they were supposed to do on Tuesday under a EU-brokered deal with international monitors deployed in Ukraine.
The row between the former Soviet neighbors - over debt and a gas price for 2009 - has affected 18 countries that were forced to close down factories, schools and left households without heating in winter cold.
Kostelka said the Czech Republic as the current EU presidency would push for the Nabucco pipeline, to pump Caspian natural gas to Europe circumventing Russia, to be built as soon as possible.
"...Nabucco is a European project. It needs to be implemented as soon as possible," Kostelka told a news conference in Moscow without giving any timeframe.
Earlier reports said the construction of the $7-8 billion Nabucco pipeline - expected to link energy-rich Central Asia to Europe through Turkey, Bulgaria, Romania, Hungary and Austria - has been tentatively scheduled to begin in 2010.
Experts, however, said the pipeline could run into difficulties, if Turkmenistan, a major natural gas producer in Central Asia, refuses to support the project.
Echoing the statement, Franco said the EU currently has no alternative to Russian-supplied gas, but will find other sources in the future.
Russian gas is the only option for Europe at the moment, but it could find other suppliers in the longer term, while a switchover to alternative sources of energy is also possible, Franco said.
"Russia and Ukraine have recently lost much of the European Union's confidence in them as economic partners. The question of political trust is growing increasingly important every day," Franco said. "Both countries seem to be blocking the solution. If the situation persists, investors could lose interest in the countries."
European Commission President Jose Manuel Barroso earlier said the situation was "incredible" and warned the EU could advise its energy firms to sue Russia and Ukraine if gas supplies were not restored.
Russia insists its gas exit points on the border with Ukraine have been opened for three days now with gas pressure along the export pipeline sufficient to immediately restart supplies.
Moscow, which has accused Kiev of blocking the transit, also urged alternative transit routes.
Russia is currently building the Nord Stream pipeline, a joint project with Germany to pump gas from Siberia to Europe under the Baltic Sea, and the South Stream pipe which will bring gas to the Balkans and onto Europe.
The Russian and Ukrainian premiers are due to meet at a gas summit in Moscow on Saturday to discuss a possible solution to the crisis.
What will be the result of the current Russian-Ukrainian ‘gas war'? (Poll)
