By Isabel Coles, Ghassan Adnan, Wall Street Journal–

The Iraqi Parliament accepted Prime Minister Adel Abdul-Mahdi’s resignation on Sunday, posing a major challenge for Iraq’s fractious political class, which must now agree on a candidate that satisfies protests roiling the country, while reconciling the competing interests of Iran and the U.S.

Pressure from the streets has been mounting since the protests broke out two months ago, with the death toll climbing toward 400 and with the risk of wider violence.

Mr. Abdul-Mahdi said Friday he would resign in response to a powerful rebuke by the country’s top cleric of his government’s handling of demonstrations after a particularly bloody day in which more than 30 people were killed. The process of choosing a new prime minister and forming a government previously has taken months, with political leaders hashing out backroom deals and the U.S. and Iran maneuvering to secure their interests. A dispute over what constituted the largest block in Parliament following last year’s election dragged on for four months until rival Shiite blocs compromised over Mr. Abdul-Mahdi.

“The problem we face now is that protesters in the street will not wait this long,” said lawmaker Wahda al-Jumaili, speaking outside the parliamentary session.

It will prove difficult to satisfy protesters whose initial demands for better governance, jobs and an end to corruption have hardened into calls for the ousting of political parties that have dominated Iraq since it became a democracy 16 years ago.

Protesters also strongly reject foreign influence in Iraqi affairs. Iraq has become one of the main arenas for competition between the U.S. and Iran as tensions increased after the Trump administration unilaterally withdrew from the Iran nuclear deal last year. For Iran, keeping its allies in power in Iraq is of vital importance as it comes under pressure from U.S. sanctions that have deepened economic problems. The outcome of Iraq’s political crisis is of crucial importance to the U.S., which has around 5,000 troops in the country and sees Iraq as crucial for preventing a resurgence of Islamic State.

“We consider [politicians] snakes: They may change their skin but never their nature,” said Bashar Hazim, who has spent the past 15 days in Tahrir Square—the epicenter of protests in Baghdad. “The current politicians have been in power for 16 years, and they ruined the country. Now it’s time for them to leave and for us to replace them—it’s as simple as that.”

At a session of Parliament on Sunday, Speaker Mohammed al-Halbousi said the president would be asked to nominate a new candidate for the premiership. According to the constitution, President Barham Salih will have 15 days to nominate a new prime minister put forward by the largest block in Parliament. That candidate will then have 30 days to submit a cabinet for approval by parliament. Mr. Abdul-Mahdi will remain as caretaker until a new government is formed. If the parties fail to agree on a candidate within the given period, the president has an additional 15 days to nominate another candidate.

“Where do you go to get a person who has not been in the political process, who has the skills to lead the country at one of the most decisive and critical junctures?” said Abbas Kadhim, the director of the Iraq Initiative at the Atlantic Council.

The names of several potential candidates began to circulate after Mr. Abdul-Mahdi said he intended to resign. The press officer of former Prime Minister Nouri al-Maliki—who was in office when a large part of the country was overrun by Islamic State—on Saturday denied rumors he was seeking to return to office.

“We hope the resignation will ease tensions,” said Hassan al-Kaabi, the head of the Badr Organization’s bloc, which is close ties to Iran, in parliament.

Even as protesters rejoiced at Mr. Abdul-Mahdi’s resignation, they remained in the streets of Baghdad and southern cities over the weekend to maintain pressure on the government.

“We still have a parliament to dissolve, an election law to change and a constitution to amend,” said protester Ali Riyadh. “We won’t accept a government led by any of the corrupt figures.”

One person was killed and 10 wounded on Sunday when security forces opened fire on protesters who were approaching a bridge that leads to the heavily fortified Green Zone, where Parliament and other government offices are located.

The judiciary on Sunday issued an arrest warrant and travel ban for Lt. Gen. Jameel al-Shimmary for his role in the deaths of more than 30 protesters in the southern city of Nasiriyah on Thursday. The bloodshed prompted Ayatollah Ali al-Sistani, Iraq’s most influential spiritual authority and a key arbiter in the country’s political affairs, to urge Parliament to choose a new government.

Speaking in a prerecorded speech, Mr. Abdul-Mahdi described the violence as “very lamentable” and said his resignation had become necessary to ease tensions that have threatened to spiral into broader conflict. He had previously resisted pressure to resign, saying that would plunge the country into chaos and impede reform.

“Any attempt to kick the can down the road will be read by the protesters on the street and the consequences will be bad for everyone,” the Atlantic Council’s Mr. Kadhim said. Political leaders “cannot really play with fire and get away with it.”

Write to Isabel Coles at isabel.coles@wsj.com