Israeli Prime Minister Benjamin Netanyahu on Tuesday added his first coalition partner as he works to build a new government, agreeing to bring in a dovish rival to oversee contacts with the Palestinians in what could signal a new approach to peacemaking by the hardline leader.

Under the deal, former Foreign Minister Tzipi Livni will serve as justice minister in the next Israeli government, in charge of peace efforts with the Palestinians. Livni, who led negotiations during the last substantive round of peace talks four years ago, has a good relationship with Palestinian President Mahmoud Abbas and favors a softer line than Netanyahu.

Standing alongside Livni at a news conference Tuesday evening, Netanyahu vowed to make a serious attempt to reach peace under his next government. He said bringing in Livni, who has been a fierce critic, was part of his goal of forming a "wide and stable" government.

"We need a Palestinian partner and I hope we will find a Palestinian partner who will take seriously Israel's security needs and that will be willing to end the conflict once and for all. Today Israel outstretches its hand to peace once again," he said.

Netanyahu, who has come under heavy criticism, both at home and abroad, for the deadlock in peace efforts during his previous term, has promised to take a more aggressive approach under his next government. But he has given no details on whether he is prepared to make any new concessions, and it remained unclear whether Livni's addition to his Cabinet would be enough to lure the Palestinians back to negotiations.

"What is important is the policies that will be adopted and implemented by the incoming Israeli government," said Yasser Abed Rabbo, a top adviser to Abbas. He said that if Netanyahu stuck to his policies of building settlements on occupied land, "it's better for Livni to search for another mission."

As foreign minister, Livni served as the chief negotiator with the Palestinians under former Prime Minister Ehud Olmert. While both sides have said they made great progress during that time, the talks collapsed in late 2008 and have remained virtually frozen since Netanyahu took office early the following year.

The Palestinians have refused to negotiate with Netanyahu while he continues to build Jewish settlements in the West Bank and east Jerusalem, areas captured by Israel in the 1967 Mideast war. The Palestinians claim both areas, along with the Hamas-ruled Gaza Strip, for their future state.

The Palestinians also want negotiations to resume from the point where they broke off under Olmert and Livni. Olmert has said he offered a near total withdrawal from the West Bank and shared control over Jerusalem.

Netanyahu has said these concessions were far too generous and that negotiations should begin without any preconditions. He also has claimed that even when he imposed a partial freeze on settlement construction, the Palestinians did not enter substantive negotiations.

But after four years of deadlock, the international community has grown impatient with the Israeli leader. In a sign of the international disapproval, the U.N. General Assembly overwhelmingly voted in November in favor of an independent Palestinian state in all of the West Bank, east Jerusalem and Gaza. Although largely symbolic, the vote signified an international endorsement of key Palestinian demands on future borders.

With President Barack Obama scheduled to visit in late March, Netanyahu is eager to present a new face to the international community. Livni's addition to his Cabinet is a step in that direction. In addition to her good working relationship with the Palestinians, Livni is well known and well respected around the world, and has appeared on lists of the world's most influential women compiled by magazines like Forbes and Time.

After the 2009 election, Livni served as opposition leader as head of the Kadima Party. But after losing a party primary last March, she stepped down and formed a new party, "The Movement," to run in the Jan. 22 election.

Livni ran on a platform committed exclusively to reviving peace efforts with the Palestinians, criticizing Netanyahu for being intransigent and saying that a peace deal is the only way to ensure Israel's long-term survival. Many Israelis, including Livni, believe that due to the rising Palestinian birthrate, Israel could become an apartheid-like state, in control of millions of disenfranchised Arabs, if it does not relinquish occupied territories.

Livni's party had a disappointing performance in the election, winning just six seats in the 120-member parliament. With little leverage, Livni appeared eager to reach a deal to enter the Cabinet. Even so, she insisted she would not join Netanyahu's government unless she was convinced he was serious about pursuing peace.

"The commitment to the peace process and the trust we were given that we would fight for it led to this partnership — a partnership that blossomed after I was given the authority to negotiate on behalf of the Israeli government with a goal of ending the conflict with the Palestinians based on two nation-states," she said.

In addition to her peacemaking role, Livni will also serve as justice minister. Her party colleague, former Labor Party leader Amir Peretz, is slated to become environment minister.

Since the Jan. 22 election, Netanyahu has struggled to form a coalition. His Likud-Yisrael Beitenu bloc won 31 seats, making it the largest faction in parliament but far short of the needed 61-seat majority. With Livni, he now controls 37 seats, still well below the majority.

The addition of Livni could now encourage other potential partners to fall in line.

But his two largest potential partners, the centrist "Yesh Atid" and the pro-settler "Jewish Home," have been driving a hard bargain. Without the support of at least one of them, it will be virtually impossible to secure a majority. Netanyahu has until mid-March to form a government.