No terrorist 'safe haven' in North Africa? That's a tall order.

After more than a decade of interventions as far-flung as the Hindu Kush, the banks of the Tigris River, and the wadis of Yemen, Washington and its allies are suddenly staring at another remote Islamic militant "sanctuary" – this time the size of the continental United States. 

“Terrorists should be on notice that they will find no sanctuary, no refuge, not in Algeria, not in North Africa, not anywhere,” said US Defense Secretary Leon Panetta last Friday in London. He was speaking as the Algerian army attacked Islamist militants holding dozens of foreign and Algerian hostages at a remote gas plant in the Sahara desert.

As violence surges in both Algeria and Mali, where France is leading an intervention against Islamists in the north, leaders are vowing to clean up North Africa. That’s easier said than done, say analysts, and would require far more than just hunting down fighters.

North Africa’s problems are manifold and interlinked. Widespread unemployment, corruption, poor governance, and lawlessness have offered Islamist militants a foothold. Frustrated young men make good recruits, while criminal networks can be tapped as sources of funding.

“It’s a mistake to put an anti-terrorism framework on a situation that is full of drug trafficking, human trafficking, and other problems,” says Amel Boubekeur, a North Africa expert at the Doha branch of the Brookings Institution, a foreign affairs think tank. Governments “really need a broad picture of stabilizing the region.”

Vast region

The region at stake is among the world’s more vast and complex. It’s roughly the size of the continental US, stretches from the shores of the Mediterranean to the scrubland south of the Sahara, and takes in a dozen or so countries – no one has yet defined a list. Some key ones, going counter-clockwise, are Libya, Tunisia, Algeria, Morocco, Mauritania, Mali, Niger, and Nigeria.

Their inhabitants include Arabs, Berbers, Tuareg, and sub-Saharan peoples. They live mainly around the fringes of the Sahara, and within borders drawn by European colonizers. National identities have developed, but sometimes compete with ethnic and tribal ones.

Unemployment is high across the region. In many countries, people have fled the hinterlands to seek jobs in cities, which are increasingly sprawling and crowded. Governments often struggle to provide public services, hampered variously by empty coffers, corruption, or incompetence.

There are emerging but fragile democracies in Tunisia and Libya, where dictators were overthrown in 2011. Elsewhere, militaries sometimes influence politics; Mauritania and Mali have had three military coups between them in the past decade.

Ethnic tensions have boiled over in Mali, where Tuareg rebels have complained of under-development and demanded their own state. Things took a new turn last year when Islamists capitalized on a fresh Tuareg revolt to shove the Tuareg aside and seize Mali’s north for themselves.

The crisis triggered a military coup that unseated Mali’s president, currently replaced by an interim president pending elections. Two weeks ago, a sudden Islamist advance and a distress call from Mali prompted France to launch air strikes and send in ground troops to lead a military intervention.

France, Mali, and their allies can expect a long struggle, says William Lawrence, who heads the North Africa Project for the International Crisis Group, a Brussels-based think tank. Islamist militants “have insinuated themselves into the fabric of the northern economy and politics,” Mr. Lawrence says. “That’s going to be hard to unravel.”

Algerian civil war 

Islamist militancy in North Africa originated largely in the Algerian civil war of the 1990’s, which pitted the government against Islamist insurgents. A breakaway group has continued to stage bombings and kidnappings, and in 2007 renamed itself Al Qaeda in the Islamic Maghreb (AQIM).

Today AQIM operates both in Algeria and northern Mali, where it does a lucrative business in kidnaps for ransom. Across the region, other groups with similar ideologies have arisen. AQIM and two other such groups are currently holding northern Mali.

Operational links to Al Qaeda’s central leadership are loose, says Lawrence. Overall, Al Qaeda today “is not a top-down organization,” he says. “There are branches in Yemen, the Gulf countries, North Africa, and so on. These gin up [their own] operations, which get blessed at some point.”

On the ground, militants’ intents, membership, and loyalties aren’t always clear, and are subject to change. In a recent twist of Islamist soap opera, a powerful AQIM commander named Mokhtar Belmokhtar fell out with his superiors last year and set up his own group, “The Masked Ones,” still pledging allegiance to Al Qaeda’s central leaders. (It’s unknown whether the sentiment is reciprocated.)

Mr. Belmokhtar has claimed responsibility for last week’s gas plant attack in Algeria, carried out with demands that France halt its intervention in Mali. Algerian forces gained control of the plant over the weekend, but not before at least 37 foreign hostages and one Algerian hostage had been killed, according to Algerian authorities.

As information on the attack and its victims seeped out of Algeria, British Prime Minister David Cameron called on Sunday for a “global response.”

Gravy training

Western governments can start by avoiding past mistakes, says Mrs. Boubekeur, from the Brookings Institution. The US, for example, had poured millions of dollars into counter-terrorism training for the Malian and Algerian armies over the past decade, to mixed effect at best.

“What they didn’t realize is that for these armies, it’s only a way to get political backing – it’s not about being efficient on the ground,” she says. Similarly, in some countries including Mali, much foreign aid cash has been milked away over the years to empower elites.

“The core issue is that this can’t only be about an anti-terrorism strategy,” Boubekeur says. “It must be about building strong and accountable institutions.”

Lawrence, from the International Crisis Group, also stresses the need to address both Islamist militancy and the other problems that help fuel it. In this, North African governments have a crucial role to play.

“Local countries should decide what kind of response is needed,” he says. “We’re in a saber-rattling moment, especially in Europe. That can lead to making mistakes.”