Cradling a rifle, dressed in a military uniform and with a desert in the background, Yevgeny Prigozhin had a message for Africa.

His Wagner group of mercenaries was “making Russia even greater on every continent – and Africa even more free”. “Justice and happiness for the African nations,” he declared.

The video, thought to be recorded in Mali, was released on Monday. Two days later, the Wagner leader was reported to have died in a plane crash in Russia.

What now for his purported mission in Africa?

Wagner has been active in several countries on the continent – most notably the Central African Republic (CAR) and Mali. But for many African governments, Prigozhin’s announced death is a relief.

I would argue that his operatives did not spread freedom, and foreign mercenaries are an embarrassment for many states – Prigozhin was a reminder of a painful past.

At the height of the Cold War, and especially shortly after independence on the continent, mercenaries were regularly used to influence the civil wars and violence that followed.

Col Callan in Angola; Bob Denard in Congo’s Katanga and later the Comoros; “Mad” Mike Hoare in Katanga and later the Seychelles; American Robert Mackenzie in Sierra Leone and British Simon Mann’s failed “organised regime change” mission in Equatorial Guinea in 2004: all these are uncomfortable history.

When I discussed Prigozhin with Russian African analysts in Moscow in late 2019, they reminded me that for them, he was less of the above, but more akin to the British imperialist Cecil Rhodes, who was out to make a fortune, and that I should not be judgmental, given the UK’s history.

Prigozhin’s Wagner footprint in Africa was built on blood and treasure – contracts giving access to valuable resources were made in payment for military support.

I had witnessed similar Private Military Companies (PMCs) in action some 20-plus years ago: Sandline International in Sierra Leone and Executive Outcomes in Angola.

They provided security and training in exchange for payment in management of mines, oil and other natural resource endowments.

Their success dramatically varied, depending on the client and the contract.

There is nothing unique about Wagner and its operational behaviour in Africa.

When I met with some of its operatives in Moscow in 2019, they were traumatised and seeking compensation for a mission in Mozambique that went badly wrong.

This was the antithesis to the Prigozhin-funded movie Granit that premiered on the pro-Kremlin NTV channel in December 2022. It depicted a group of Russian hero “military instructors” invited to Mozambique to fight Islamic State-linked insurgents in the country’s north.

Its operations in Libya, Sudan, Mali and CAR have produced mixed results.

Wagner’s greatest military success is probably acting as a Praetorian guard for the presidency and foiling a military coup in CAR’s capital, Bangui.

Its greatest failure: possibly in Mozambique. Wagner deployed there in September 2019 for counter-insurgency operations, but the killing of seven of its personnel and 20 Mozambican special forces in October in a friendly fire exchange resulted in their withdrawal in early 2020.

Wagner’s investments in fake news and trolling, encouraging deeper anti-Western sentiment in West Africa, have been more successful than its efforts to win elections in Madagascar, Mozambique or Zambia.

It is currently most militarily active in Sudan and Mali.

Wagner has had a presence in Sudan since 2017, providing security services and overseeing gold mining concessions.

The US Treasury Department alleges that Wagner has also been supplying Sudan’s Rapid Support Forces with surface-to-air missiles recently.

In September 2021, the Malian junta struck a security agreement with Wagner for the deployment of 1,000 personnel at a monthly cost of $10.8m (£8.6m).

The Wagner Group’s counter-terrorism performance has been underwhelming and there are allegations of serious human rights abuses by them, especially in central Mali.

Although the group’s deployment in Mali has provoked criticism from the region and the African Union (AU), Wagner still sought to expand its operations to Burkina Faso.

An offer in late 2022 was rejected, but Russia continues to woo the junta, whose leader Captain Ibrahim Traore attended the second Russia-Africa summit in St Petersburg in July this year. Burkina Faso is one of six African countries to receive free grain from Moscow.

Soon after the September 2022 coup in Burkina Faso that resulted in Capt Traore taking over the military government, Prigozhin described him as “a truly courageous son of the motherland”.

The Wagner leader also hailed Niger’s military coup in July this year as good news and offered his fighters’ services to bring order.

But in the wake of his failed uprising in Russia in June, Wagner’s grip on its African operations was under threat.

According to President Vladimir Putin, Prigozhin had returned to Russia from Africa on the day of his death and had gone to meet Russian officials in Moscow. It seems he may have been trying to preserve his Wagner Africa portfolio from full Kremlin takeover.

Mr Putin described Prigozhin as a talented person.

“[He] worked in our country, but also abroad, in Africa. He worked with oil, gas, with precious metals,” the president said.

Pan-African dismay about mercenaries began as soon as they became active in the decolonisation conflicts of the 1960s. In 1977, the African Convention on Mercenarism was signed in Libreville and took effect in April 1985.

In February 2022, the African Union’s commissioner for political affairs, peace and security, Bankole Adeoye, called for the “complete exclusion of mercenaries from the African continent”.

These conventions may be ineffective, but an increasing number of African governments do not want a repeat of the use of foreign mercenaries on African soil to pursue geopolitical rivalries of external powers that occurred during the Cold War.

Mozambique discovered that the use of private military contractors was not so effective and turned to Rwanda for assistance.

Mozambican President Filipe Nyusi concluded that an effective, disciplined military was needed to assist his own armed forces, and the Rwandan Defence Forces (RDF) has been successful, significantly reducing the insurgency.

The worsening security situation across the Sahel also resulted in Nigerian President Bola Tinubu, along with West African allies, drawing up plans for the strengthening of a regional standby force – in effect, a regional counter-terrorism and anti-coup force.

The African-led and designed security initiatives are an explicit rejection of mercenaries.

But for those military governments in the region, in Mali, Burkina Faso and now Niger, the Russian operatives may be an attractive alternative.

Wagner, if it survives, or other emerging Russian mercenary groups, will increasingly find the market limited to putschist regimes using them as the security partner of last resort.

The Kremlin, which will not desert the likes of CAR and Mali, is likely to try to take over operations, but its ability to seriously take on new clients, as Prigozhin had envisioned, will be difficult.

This is the moment for African leaders to truly implement African solutions to African problems, by implementing its conventions and building up institutions and credible, accountable security forces.

Alex Vines directs the Africa Programme at the Chatham House think tank.