(Adds party talks under way)
By Douglas Hamilton
JERUSALEM, Feb 11 (Reuters) - Israel headed for political gridlock on Wednesday with both sides declaring victory in an election that left the prospect of Israel and the Palestinians making peace as distant as ever.
Foreign Minister Tzipi Livni's centrist Kadima party won the most votes but had little chance of building enough support for a resilient coalition government. Right-wing opposition leader Benjamin Netanyahu can get the backing in parliament, but analysts said the likely alliance would prove dysfunctional.
"I won," read the headline of the country's biggest newspaper, Yedioth Ahronoth, over photographs of both leaders. But to some commentators, the rival claims showed that Israel, deeply beset with divisions over constitutional issues and years of failed diplomacy with Arabs, had lost.
"One thing is clear to all Israeli voters," said the paper's Eitan Haber. "The political system is shattered."
Washington signalled equanimity. The new administration of U.S. President Barack Obama wants to revive peace talks to give the Palestinians a state alongside Israel, provided they can repair a schism triggered by Islamist Hamas's hold on Gaza.
"We certainly hope that a new (Israeli) government will continue to pursue a path to peace. I see no reason to think a new government would do something otherwise," State Department spokesman Robert Wood said.
Israeli President Shimon Peres must now decide whether to call on Livni or Netanyahu, who then has 42 days to form a government. An official election tally is due out by Feb. 18, after which Peres would have a week to make his nomination.
As the parties began negotiating possible pacts, Israeli media said it seemed Peres would have no choice but to tap Netanyahu if the majority rightists all back him.
But it would be the first time in Israel's 60-year history that the winner of an election would be passed over.
The results, not yet official, gave Netanyahu 27 seats in the 120-seat Knesset, while Livni's Kadima won 28.
She said she would be prime minister and invited Netanyahu to join a "unity government". But Netanyahu said he would lead the "nationalist camp" in parliament, and control 64 seats.
"With God's help I will lead the next government," Netanyahu, 59, told supporters of his Likud party.
"Tzipi Livni has only the slightest chance, or none at all, of forming a government under her leadership," said Abraham Diskin, a political scientist at Jerusalem's Hebrew University.
HARD RIGHT IN PIVOTAL POSITION
Avigdor Lieberman's far-right Yisrael Beiteinu party, which surged to third place in the ballot with its demand to test the loyalties of Israeli Arabs, emerged as a potential kingmaker.
He met Livni and Netanyahu on Wednesday, appearing to favour the latter though he deferred any decision. Another linchpin party, the conservative Shas, held it own talks with the Likud.
"We want a nationalist government. We want a rightist government," Lieberman said. A deal was needed as fast as possible because the state "has been paralysed for half a year".
"People may not be aware, but we are still without a budget ... in conditions of global financial crisis," Lieberman said.
Netanyahu had been cruising ahead in opinion polls until Olmert's centre-left coalition, including Livni, launched a military offensive against Hamas and other factions in the Gaza Strip, to stop them firing rockets at towns in southern Israel.
The 22-day January war cost 1,300 Palestinian lives versus 13 Israelis killed, but had massive public support. After a truce on Jan 18, the election campaign resumed as Israel pursued Egyptian-brokered talks with Hamas on a durable Gaza truce.
The ceasefire talks are still going on, and uncertainty in Israel will not stop them, both sides said on Wednesday.
European Union foreign policy chief Javier Solana said Israel's next government must also restart serious talks on a comprehensive peace deal, and could not let them stagnate.
"I think if we continue in a crisis management mode, if we don't enter into a conflict resolution mode it will be going back and back again," Solana told Reuters.
Livni, 50, led the main peace talks last year with the Palestinian Authority of President Mahmoud Abbas, and would try to revive them. Netanyahu is cooler on the key trade-offs for an accord -- ceding occupied land and curbing Jewish settlement.
Lieberman and religious parties in a coalition would be likely to set virtually impossible conditions for a peace deal.
The Palestinian Authority, which governs the occupied West Bank, said that whoever ends up in charge Israel is obliged to continue talks and to meet international obligations.
"The ascent of the Israeli right does not worry us," Abbas told Italy's La Repubblica newspaper. "In whatever form, the government, once in power, will ultimately end up with responsibility, pragmatism prevailing."
But many Palestinians were gloomy. "Israelis voted for the right and against peace," said office worker Ali Zaidan. "We will not see progress in the peace process in the coming years." (Additional reporting by Sue Pleming in Washington; Editing by Peter Millership) (For blogs and links on Israeli politics and other Israeli and Palestinian news, go to blogs.reuters.com/axismundi)