KIEV, Ukraine—Ukraine agreed Wednesday to extend the lease of Russia's Black Sea Fleet base in return for sharply lower natural-gas prices, a long-term trade-off that reasserts much of Moscow's influence over its former Soviet neighbor after years of tension.
The deal was the latest sign of Russia's determination to use its vast energy resources to restore dominance lost when the Soviet Union collapsed in 1991. It will allow Russia to keep a strategic military presence beyond its borders until 2043, a quarter-century beyond the end of its current lease for the naval base on Ukraine's Crimean peninsula.
Ukraine, hit hard by the global economic downturn, received a waiver of export taxes that will knock as much as 30% off the price of Russian gas over the next nine years, avoiding disputes that have often led to midwinter gas cutoffs.
The commitments were a clear sign that Ukrainian President Viktor Yanukovych, who took office two months ago, is moving the country closer to Moscow after years of rule by pro-Western leaders of Ukraine's Orange Revolution. Some of those politicians, now in opposition, condemned Mr. Yanukovych's concession on the naval base as a sellout of Ukraine's sovereignty.
Mr. Yanukovych and his Russian counterpart, Dmitry Medvedev, announced the accords after meeting in the Ukrainian city of Kharkiv. Mr. Medvedev told a joint news conference that the gas and base accords were linked. "This was a step we have awaited for a long time," he said of the base extension. In return, he said, "our Ukrainian partners will receive a discount in the price of gas."
Ukraine, a country of 46 million people wedged between Russia and the European Union, has struggled to balance its relations with the two since independence in 1991. Mr. Yanukovych's predecessor, Viktor Yushchenko, infuriated Moscow by trying to kick the fleet out of Ukraine, calling it a hostile presence.
The Black Sea Fleet was once part of the Soviet navy and remained in Ukraine under the Russian flag. The current lease on the base was signed in 1996.
Mr. Yanukovych, who has abandoned his predecessor's goal of bringing Ukraine into the North Atlantic Treaty Organization, now risks alienating a large part of his compatriots by allowing the fleet to stay. Former Prime Minister Yulia Tymoshenko, who leads Ukraine's largest opposition party, said the decision violates a constitutional prohibition on foreign military bases in Ukraine—a ban that allows exceptions for stationing troops under a temporary lease.
"It's not just treason," she said. "It's the start of the systematic destruction of the independence of our state."
Ukraine's Foreign Ministry issued a statement saying: "We do not regard the Black Sea Fleet as a source of threat to Ukraine's sovereignty and territorial integrity."
Mr. Medvedev said the fleet's continued presence would provide "a greater, better guarantee for European security in the Black Sea basin."
The base extension will have repercussions for other former Soviet republics. The fleet, consisting of about 40 combat vessels, provided maritime support for Russian ground forces during a brief war with Georgia in 2008 and sank a Georgian vessel carrying missile launchers.
Russia on Wednesday also confirmed it plans to buy a French Mistral-class warship, according to state news agency RIA-Novosti, a vessel capable of carrying tanks and helicopters and conducting an amphibious landing.
Georgian President Mikheil Saakashvili, who was in the U.S. for a nuclear security summit, called Wednesday's moves further signs of an expansionist Moscow agenda. Russian Prime Minister Vladimir Putin, he said in an interview, "doesn't make any secret of trying to restore some kind of Soviet empire... Ukraine, more or less from their point of view, has been fixed."
"I hear lots of talk [in the U.S.] that the Cold War is over," he said. "It might be over for America, but certainly it's not over for Vladimir Putin."
For Russia, the price of Ukrainian cooperation will amount to billions of dollars in export duties from which Kiev will be exempted. Ukraine has been paying $330 per 1,000 cubic meters of Russian gas under a 10-year agreement on a market-based pricing scheme signed last year.
Mr. Yanukovych called the accord an unsustainable burden on Ukraine's economy, which shrank 15% last year, and pledged during his election campaign to renegotiate it.
The new gas deal, signed Wednesday by Russian gas exporter OAO Gazprom and Ukraine's state energy firm Naftogaz, will waive export duties on 30 billion cubic meters of gas that Ukraine will buy this year and on 40 billion cubic meters it expects to buy in subsequent years until 2019.
Gazprom said the discount will be 30% of the market-based price but not more than $100 per 1,000 cubic meters. Dragon Capital, a Kiev-based investment bank, estimated that the price cut will save Ukraine about $1.5 billion this year.
That will allow the country's new government to adopt a budget for this year and secure renewed lending from the International Monetary Fund, officials said. Deputy Prime Minister Serhiy Tihipko will head to Washington on Thursday to present an economic-growth plan to the IMF, which last year suspended a $16.4 billion loan program after large social-spending increases were passed into law.
Gazprom's chief executive, Alexei Miller, said the company's profits will be unaffected by the new arrangement. He also said that under the deal, Ukraine won't pay penalties if it buys less gas the agreed in the contract.
"This deal is a win for everyone," said Matthew Saegers, a Eurasian energy specialist at Cambridge Energy Research Associates. "Gazprom wins because it maintains its profitable position. Ukraine gets a reduction in price. And the Kremlin gets what it wants—to show that it's the deal maker and geopolitical master in this part of the world."