The greatest challenge to Russian President Vladimir Putin in his more than two decades in power fizzled out relatively peacefully Saturday after the rebellious mercenary commander who ordered his troops to march on Moscow abruptly reached a deal with the Kremlin to go into exile and sounded the retreat.

The dramatic if brief revolt shifted the landscape for the Kremlin and the 16-month-old war in Ukraine and prompted Russia to pull soldiers back from the battlefield to defend the capital, a stunning recognition of the threat posed by Wagner Group soldiers under the command of Yevgeny Prigozhin.

Under the deal announced by Kremlin spokesman Dmitry Peskov, Prigozhin will go to neighboring Belarus and charges of mounting an armed rebellion will be dropped. The government said it also would not prosecute fighters who took part, while those who did not join in were to be offered contracts by the Defense Ministry.

Putin had vowed earlier to punish those behind the armed uprising led by his onetime protege, whose forces seized a key military facility in southern Russia before advancing on the capital. In a televised speech to the nation, he called the rebellion a “betrayal” and “treason.”

In allowing Prigozhin and his forces to go free, Peskov said, Putin’s “highest goal” was “to avoid bloodshed and internal confrontation with unpredictable results.”

Moscow had braced for the arrival of the Wagner forces by erecting checkpoints with armored vehicles and troops on the city’s southern edge. Red Square was shut down, and the mayor urged motorists to stay off some roads.

About 3,000 Chechen soldiers were pulled from fighting in Ukraine and rushed there early Saturday, state television in Chechnya reported, signaling the Kremlin’s desperation as the Wagner troops advanced to, according to Prigozhin, just 200 kilometers (120 miles) from Moscow.

But after the deal was struck, Prigozhin announced that he had decided to retreat to avoid “shedding Russian blood.” His troops were ordered back to their field camps in Ukraine, where they have been fighting alongside Russian regular soldiers.

Prigozhin has demanded the ouster of Defense Minister Sergei Shoigu, long the target of his withering criticism for his conduct of the war in Ukraine. On Friday, he accused forces under Shoigu's command of attacking Wagner camps and killing “a huge number of our comrades.”

Prigozhin did not say whether the Kremlin had responded to his demand. Peskov said the issue could not have been discussed during the negotiations, which were conducted by the president of Belarus, and is the “exclusive prerogative of the commander in chief.”

If Putin were to agree to Shoigu’s ouster, it could be politically damaging for the president after he branded Prigozhin a backstabbing traitor.

Early Saturday, Prigozhin’s private army appeared to control the military headquarters in Rostov-on-Don, a city 660 miles (over 1,000 kilometers) south of Moscow, which runs Russian operations in Ukraine, Britain’s Ministry of Defense said.

Read: After day of drama, Wagner chief orders troops to halt march on Moscow

A nighttime video from the city posted on Russian messaging app channels showed people cheering Wagner troops as they left Rostov-on-Don. Prigozhin was seen riding in one of the vehicles, and people greeted him and some ran to shake his hand as he lowered the window. The regional governor later said that all of the troops had left the city.

Wagner troops and equipment also were in Lipetsk province, about 360 kilometers (225 miles) south of Moscow.

Authorities declared a “counterterrorist regime” in Moscow and its surrounding region, enhancing security and restricting some movement. On the southern outskirts, troops erected checkpoints, arranged sandbags and set up machine guns. Crews dug up sections of highways to slow the march.

Moscow Mayor Sergei Sobyanin declared Monday a non-working day for most residents as part of the heightened security, a measure that remained in effect even after the retreat.

The dramatic developments came exactly 16 months after Russia launched its full-scale invasion of Ukraine, Europe’s largest conflict since World War II, which has killed tens of thousands, displaced millions and reduced cities to rubble.

Ukrainians hoped the Russian infighting would create opportunities for their army to take back territory seized by Russian forces.

Ben Barry, senior fellow for land warfare at the International Institute for Strategic Studies, said that even with a deal, Putin’s position has probably been weakened and “these events will have been of great comfort to the Ukrainian government and the military.”

Ukrainian President Volodymyr Zelenskyy said late Saturday, shortly before Prigozhin announced his retreat, that the march exposed weakness in the Kremlin and “showed all Russian bandits, mercenaries, oligarchs” that it is easy to capture Russian cities “and, probably, arsenals.”

Switching into Russian in his daily video address, Zelenskyy said “the man from the Kremlin” was “very afraid.” He repeated his calls for the West to supply Ukraine with F-16 fighter jets and ATACMS tactical ballistic missiles.

Prigozhin had vowed earlier that his fighters, whom he said number some 25,000, would not surrender because “we do not want the country to live on in corruption, deceit and bureaucracy.”

“Regarding the betrayal of the motherland, the president was deeply mistaken. We are patriots of our homeland,” he said in an audio message on his Telegram channel.

He posted video of himself at the military headquarters in Rostov-on-Don and claimed his forces had taken control of the airfield and other military facilities in the city without any deaths or even “a single gunshot.”

Russian media, however, reported that several helicopters and a military communications plane were downed by Wagner troops. The Kremlin referred a question about the losses to the Defense Ministry, which has not commented.

The short-lived rebellion came as Russia is “fighting the toughest battle for its future,” Putin said, with the West piling sanctions on Moscow and arming Ukraine.

“The entire military, economic and information machine of the West is waged against us,” Putin said.

Read: Wagner forces advance toward Moscow despite Putin's warning

State-controlled TV networks led their newscasts with Putin’s statement and reported the tense situation in Rostov-on-Don. Broadcasters also carried statements from top Russian officials and lawmakers voicing support for Putin, condemning Prigozhin and urging him to back down.

Chechen strongman Ramzan Kadyrov, who in the past has sided with Prigozhin in his criticisms of Russia’s military, also expressed support for Putin’s “every word.”

“The mutiny needs to be suppressed,” Kadyrov said.

Wagner troops have played a crucial role in the Ukraine war, capturing the eastern city of Bakhmut, an area where the bloodiest and longest battles have taken place. But Prigozhin has increasingly criticized the military brass, accusing it of incompetence and of starving his troops of munitions.

In announcing the rebellion, Prigozhin accused Russian forces of attacking the Wagner camps in Ukraine with rockets, helicopter gunships and artillery. He alleged that Gen. Valery Gerasimov, chief of the General Staff, ordered the attacks following a meeting with Shoigu in which they decided to destroy the military contractor.

The Defense Ministry denied attacking the camps.

The 62-year-old Prigozhin, a former convict, has longstanding ties to Putin and won lucrative Kremlin catering contracts that earned him the nickname “Putin’s chef.”

He gained attention in the U.S. when he and a dozen other Russian nationals were charged with operating a covert social media campaign aimed at fomenting discord ahead of Donald Trump’s 2016 presidential election victory. Wagner has sent military contractors to Libya, Syria, several African countries and eventually Ukraine.

The rebellion appeared likely to further hinder Moscow’s war effort in Ukraine, as Kyiv’s forces probed Russian defenses in the initial stages of a counteroffensive.

Orysia Lutsevych, the head of the Ukraine Forum at the Chatham House think tank in London, said the infighting could create confusion and potential division among Russian military forces.

“Russian troops in Ukraine may well now be operating in a vacuum, without clear military instructions, and doubts about whom to obey and follow,″ Lutsevych said. “This creates a unique and unprecedented military opportunity for the Ukrainian army.”

Read more: Russia's Wagner boss says more than 20,000 of his troops died in Bakhmut battle