I still vividly remember President Barack Obama’s speech in Cairo on June 4, 2009, delivered just five months into his first term of office. It conveyed an ambitious vision for reshaping America’s relationship with the Muslim World. He acknowledged that the colonial legacy had fueled mistrust of the West, and that during the Cold War, Muslim countries were treated as proxies without regard to their own aspirations. “I’ve come to Cairo to seek a new beginning between the United States and Muslims around the world, one based upon mutual interest and mutual respect,” Obama told us. We in Egypt and the Middle East welcomed a new American policy based on understanding and dialogue.

Obama emphasized multilateralism in his foreign policy. This was an encouraging development after the unilateralist policies of his predecessor, President George W. Bush, whose War on Terrorism had led to invasions and long occupations of Afghanistan and Iraq. Obama adopted a strategy of engagement, cooperation, negotiation, and persuasion. Yet as a realist Obama did not exclude a willingness to use force if American core interests were threatened. Some dubbed his policy “multilateralism with teeth.” Whatever Obama’s intentions, however, multilateralism has not necessarily produced good results.

In handling the wars in Afghanistan and Iraq, inherited from his predecessor, Obama preferred a blend of unilateralism and multilateralism. In an attempt to reconcile U.S. foreign policy with international law, Obama ordered a swift and complete withdrawal of U.S. troops from Iraq. In Afghanistan, where U.S. operations had NATO support, Obama ordered a surge of U.S. troops before calling for a phased withdrawal. However, in both countries, U.S. pullback has led to a precarious security situation and the potential for complete collapse.

Obama seemed to be at his multilateral best in response to the Libyan uprising in 2011. He achieved a United Nations Security Council resolution allowing the “use of all measures” to intervene in Libya’s domestic conflict to prevent human rights violations. NATO eventually took the lead in a military effort that effectively supported armed rebel factions until Libyan dictator Muammar Gaddafi was overthrown. But Obama’s interventionism in Libya would later come under intense criticism as the country disintegrated into factional warfare; some questioned whether Western intervention was necessary at all, and others blamed a premature NATO withdrawal for leaving the country with weak institutions.

Arguably, the mission creep that occurred in Libya—from protecting civilians to overthrowing a ruler—undermined Washington’s attempts to replicate multilateral intervention in response to another Arab Spring uprising in Syria. Obama called for UN intervention in Syria two years after revolts began, and only when the alleged use of chemical weapons challenged the international body’s responsibility to act against Bashar Al-Assad. But when the White House failed to mobilize consensus for military action in the Security Council, it agreed to Russia’s proposal to place Syria’s chemical weapons under international control. Causal effects are difficult to assess, but a lack of targeted military intervention opened up space for other forces, such as the extremist group known as the Islamic State in Iraq and Syria (ISIS).

Washington’s agreement to enter substantive negotiations with Iran over its nuclear program is a prime example of Obama’s multilateralism. The White House opened up official channels of communication with Iran, sending Secretary of State John Kerry to negotiate with Iranian diplomats during P5+1 talks about the country’s nuclear program. This is a significant reversal from George W. Bush’s “no talks” policy and threat of a pre-emptive attack. Many pressing issues demand an American dialogue with Tehran: Iran’s nuclear program; the rise of ISIS; the increasingly unstable political situation in Afghanistan and Yemen; and the repercussions of that instability on a nuclear-armed Pakistan.

A glaring exception to Obama’s multilateralism is his policy on the Palestinian-Israeli conflict. Like most of his predecessors, Obama acceded to the Israeli preference for the United States to remain the prime mediator in the dispute. After expending relatively little effort in Obama’s first term, the administration mounted a diplomatic drive in the second. U.S.-led negotiations resulted in the release of Palestinian prisoners and a Palestinian willingness to freeze an appeal for international recognition of the State of Palestine. A year later, however, talks have failed and prospects for peace are dim.

The disappointing results can be attributed partly to the magnitude and complexity of the region’s problems. Few in the administration—or in the region—were prepared for the dramatic, fast-paced developments of the past few years: the Arab uprisings; the spread of extremism and terrorism; the sectarian rivalry between Shiites and Sunnis; the escalation of violence between Hamas and Israel. These challenges were compounded by unsuccessful economic development strategies, social inequity, and persistence of poverty.

For better results, the United States must extend a multilateralist approach to the core Palestinian-Israeli conflict. Washington must not walk away, and Europeans should not remain on the sidelines. As the Obama administration moves toward a deal with Iran, it must assuage the fears of Gulf Cooperation Council countries about a realignment of American security interests. Obama must find a way to work constructively with the main players in the region to contain the threat posed by ISIS.

In his commencement address at the U.S. Military Academy at West Point last spring, Obama defined multilateralism as a legacy of his presidency. He emphasized the need to mobilize allies and partners for collective action, and lauded international organizations from the UN and NATO to the World Bank and International Monetary Fund. Even if the shift to multilateralism has not fulfilled the hopes and expectations Obama raised five years ago in Cairo, it is a potentially important milestone. But without a more consistent and effective implementation of the policy, the promise of a better American relationship with the Muslim World will remain elusive.

Magda Shahin is director of the Prince Alwaleed Bin Talal Bin Abdul Aziz Alsaud Center for American Studies and Research at the American University in Cairo