When contemplating Iraq, Americans look into a murky crystal ball. History naturally presents itself as a tool to clarify the choices and possibilities that lie before us. But what history? Before the invasion, neoconservatives soaked the capital in the rhetoric of Winston Churchill and the “lessons” of the 1930s. Later, after Saddam was found to have no weapons of mass destruction, they sought to rebrand the Iraq War as a part of the long struggle against totalitarian “Islamofascism” and thus a successor to the Cold War. For many Americans, the natural comparison is the Vietnam War, which ended with evacuation choppers on the Saigon embassy’s roof and several more years of bloodshed in Indochina.

The French war in Algeria, never well known in the United States, has its own claims to stake. Before the Iraq War commenced, some Pentagon special operations officers attended a screening of Gillo Pontecorvo’s classic 1966 docudrama, “The Battle of Algiers.” More recently, reporters were told that George W. Bush was reading Alistair Horne’s exhaustive A Savage War of Peace—a book that, Horne stated in the preface to the recent paperback edition, was Ariel Sharon’s favorite bedtime reading. (Israeli dove Amos Elon remarked that Sharon must have completely misunderstood the work.)

What lessons might Americans draw from the Algerian war? They are not obvious. The brutal conflict, which gave rise to an extraordinary memoir literature in French, impinged on France’s national life far more than Iraq has yet touched America. But some common features are clear. The Algerian war was more or less part of our own historic era, influenced by international air travel and mass communications. A Western democracy was facing off against Arab Muslims; terrorism against civilians—first employed by the Arab guerrillas and later by the French far Right—was a central aspect of the war; and the use of torture to root out the terror networks produced a moral upheaval in France. Indeed, the war very nearly cost France its democracy.

In the end, it required the extraordinary political leadership of Charles de Gaulle, who turned against some of his most devoted supporters, to extricate France from the mess and move the country forward. Losing the war proved far more painful for the Algerians who had aligned themselves with France than for France itself. If one is looking for an example of a comparatively rich and technologically superior Christian country trying to dominate an Arab land against substantial local and international opposition, Algeria surely fits the template.

Still, different people will draw different conclusions about the conflict: The Weekly Standard’s Irwin Steltzer reports (with great satisfaction) that the lesson George W. Bush has apparently imbibed from Alistair Hornes’s book is that France didn’t stay long enough!

Of course the parallel doesn’t fit perfectly. France was tied to Algeria through the presence of one million European settlers, who saw themselves as French, though they came from throughout the northern tier of the Mediterranean. Prosperous landowners, small industrialists, holders of lower middle-class city jobs, shopkeepers, (a few) manual laborers, the pied noirs were united by attachment to a privileged status French control over Algeria gave them. They had a powerful lobby in Paris, through which they exercised great influence on the appointed colonial government. A local legislature—originally created as a liberalizing reform—was designed with separate wings, one for Europeans and one for Muslims, so that any Algerian democratic initiative would be stillborn. The pied noirs secured for themselves the colony’s best land and had access to the best jobs. France devoted more resources to schooling the children of the one million pied noirs than it did to those of nine million Muslims. The two communities had little social contact and virtually no intermarriage.

The accelerating disparity between the groups’ birthrates reached into every aspect of the colony’s social system. At the time of the French conquest in 1830, the Muslim population was less than two million; it was nine or ten million at the outbreak of the insurrection—and growing fast. Any program of real integration between the two communities—one that gave every Algerian an equal right to a European to vote for representatives in Paris—would have led to Muslims becoming a powerful voting bloc in France proper. This was a fact few partisans of French Algeria were willing to face.

In May 1945, the pied-noir conceit that Algerian Muslims were content with second-class status was contradicted by a violent Muslim riot: a V-E march in the town of Sétif took on nationalist overtones, the police fired shots, and the Muslim crowd turned on the Europeans. The unrest spread quickly to neighboring towns: 103 Frenchmen were killed, often brutally. In punitive retaliation, the French used dive bombers, naval shelling, and Senegalese troops to destroy several villages, producing a Muslim death toll in the thousands. The Sétif riot and its aftermath passed almost unnoticed in France but set a pattern that would repeated as the rebellion gathered steam: the Muslims would riot or stage an attack, and the French would answer with massive and relatively indiscriminate reprisals. At the end of each round, nationalist sentiment would grow.

Months after the French defeat at Dien Bien Phu in 1954, the Algerian rebels—the FLN—then numbering fewer than a thousand, launched their first organized attacks, setting off bombs, striking isolated barracks. The ringleaders were young men of modest education, with no real ideological program beyond getting the French out. But they succeeded in igniting a war and capturing the imagination of Algeria’s youth, who in the tens of thousands proved willing to kill, suffer, and die for Algerian independence.

France responded as a sophisticated liberal Western power might be expected to. The Fourth Republic’s leaders were humanist, temperate democratic socialists, convinced that France’s ideals of liberty, combined with increases in economic and technological aid, could surmount the acknowledged evils of colonialism and bind Algeria to France. They sent Jacques Soustelle, an ethnographer first prominent as a left-wing intellectual, later a key organizer of the Resistance and an associate of de Gaulle, to govern the colony. Soustelle was determined to make France’s rule enlightened and not reactionary, to break the social and economic monopolies of the pied noirs, to make “Algérie Française” something progressive France could be proud of.

Meanwhile, the military set about to clean up the guerrillas in the countryside, and France began to pour in troops. Within a year, most of the initial FLN leadership was killed or captured. But still the rebellion managed to survive. In 1955, a handful of guerrillas incited the Muslims of Philippeville to set upon the town’s European majority with knives and axes. In an orgy of violence, the Muslims killed women and children, slitting throats, disemboweling pregnant women. The death toll was 123, including 53 Muslim “collaborators.” The French responded in kind, but more widely. The pied noirs went on a countrywide rampage, shooting Muslims in the street. American diplomats estimated the death toll of the French retaliation at 20,000.

Philippeville brought a practical end to “integration” as a concept, though it lingered on in French rhetoric. The massacre also brought a quick end to Soustelle’s liberalism; at the funeral of one slain Frenchmen, he spoke of revenge and of the “totalitarian fanaticism” of the rebels. He would end his career as a backer of the terrorist far Right trying to hold on to French Algeria at all costs.

Military means could never definitively smother the rebellion, even after France stationed half a million troops in the colony. As a character in Jean Laterguy’s war novel The Centurions put it, the guerillas were “like the algae which always comes back in aquariums.” Their chief targets were the Muslims who co-operated with the French and the most liberal representatives of the French effort, teachers and engineers. Killing was not enough. The guerrillas preferred mutilation, severing the noses, lips, and sexual organs of their victims. The purpose was to make the middle ground untenable. “France is at home here,” Soustelle had announced to the Algerian Assembly when he arrived at his post. Following Philippeville, this claim sounded ridiculous.

After one battle in which a platoon of French reservists was ambushed and wiped out, the rhetoric escalated as France sought more grandiose justification for a conflict it couldn’t face losing. French Resident Minister Robert Lacoste described the war in Algeria as “but one aspect of a gigantic global struggle, where a number of Muslim countries, before collapsing into anarchy, are trying through Hitlerian strategies to install an invasive dictatorship. … The war we are waging … is that of the Western world, of civilization, against anarchy, democracy against dictatorship.” By the third year of the war, language like this was commonplace among diplomats and intellectual partisans of Algérie Française, who increasingly depicted the conflict as “terror” against “liberty.” To justify the sacrifices of the war, much of the French political class essentially talked itself into believing that defeating the rebels in Algeria was a matter of national life and death, which of course made a negotiated withdrawal that much more difficult to contemplate.

The war reached the city of Algiers in the spring of 1956. The FLN recognized that killing French civilians in the capital was worth more, propaganda wise, than killing soldiers in the field. The memorable scenes in Pontecorvo’s docudrama tell the story well enough: attractive young Muslim women getting dressed up in Western clothes, flirting with the French soldiers, and placing bombs in the social hangouts of the gilded youth of Algérie Française. After a few months, the city yearned for martial law. Gen. Jacques Massu and a division of paratroopers were put in charge. The paras began torturing. Contrary to liberal conventional wisdom, the torture did its job, and the secret organizations of bomb makers and placers began to give up their secrets. Electrodes to the genitals—“la machine qui fait parler”—was the most effective method.

The paras won the Battle of Algiers. By the fall of 1957, the city was free of violence and would remain so for four years. And the legend of the paras in their colorful regimental berets grew: many Frenchmen would come to see them as their country’s most legitimate political force.

But elite metropolitan France—or at least its liberal intellectuals—was not willing to accept torture done in its name. Repugnance at the paras’ methods waxed during 1957, inciting an uproar in the Parisian journals. Then it waned, the mood of indignation proving impossible to sustain. By 1960, an American writer in Paris noted that among the intelligentsia, torture had become a bore—perhaps the worst fate a moral cause could suffer. Nevertheless, the debate lingered. France officially disavowed the methods that seemed necessary to defeat the guerrillas, and mainstream French political opinion began to shift toward finding the costs of staying in Algeria heavier than defeat.

Much as France sought to depict the battle as a decisive conflict between “Western civilization” and “Islamic fanaticism,” few elsewhere in the West shared the view. The Eisenhower administration remained publicly understanding toward its ally. Forging NATO and a strong Western Europe were central to its diplomacy. But when the war swelled France’s budget deficit, forcing it to seek emergency aid from Washington, Secretary of State John Foster Dulles hinted that withdrawing from Algeria would help matters. The young Sen. John F. Kennedy called openly for Algerian independence in 1957, and the chic French weekly L’Express put him on the cover. Americans of both parties feared that if the war dragged on, Communist infiltration of the North African nationalist and independence movements would become inevitable.

It was in this context that the Fourth Republic stumbled. In February 1958, a French air strike along the Tunisian frontier killed scores of civilians, and British and American diplomats offered their “good offices” to calm matters. This was widely seen as a prelude to dreaded American interference, and the army and the colons sniffed a “sellout.” A mob in Algiers, eventually backed by several key generals, seized the government buildings and put the city under the rule of a Committee of Public Safety. Rumors flew around Paris that the army would take power there too; it was not clear that in a crunch any regiments would defend the Fourth Republic against a military coup.

Charles de Gaulle was well informed of these plots through his own network—perhaps encouraging them while holding himself aloof as an arbiter between the elected government and a rebellious military. In May 1958, he was asked to form a government by Fourth Republic politicians who knew they might otherwise be swept away by a few regiments of angry paratroopers.

He was 67, too old for the job by his own reckoning. Six feet, five inches tall, his regal style was evident in both spoken and written word. His call to national resistance after the 1940 armistice had salvaged France’s honor in World War II—he had won a place for France among the war’s victors by the force of his own personality more than by France’s military contribution to the victory—and his presence in the first postwar liberation government was a critical brake on the ambitions of France’s largest organized political force, the Communists. He resigned in 1946, perhaps expecting to be summoned back. By the 1950s, his mystique still lingered, and he maintained a powerful network of devoted followers among the French political class. The first volumes of his memoirs were huge bestsellers; even without his remarkable second act, de Gaulle would have been one of the political giants of the 20th century.

But the key aspect of de Gaulle’s return as the first president of the Fifth Republic—about which most of the country was unaware—was that he was prepared from the outset to flout the wishes of the very generals and colonels who had eased his return to power. From 1946 onward, one can see a clear line in de Gaulle’s thinking: the era of colonies was finished. It could end sooner or later, gracefully or abruptly. France could retain cultural and economic ties to its ex-colonies or not. But the end of colonial rule was inevitable. And yet de Gaulle allowed many Gaullists who were fierce partisans of Algérie Française to interpret his Delphic utterings as they wished.

Having ascended to power in the slipstream of a pied-noir riot, within weeks of his investiture in Paris, he visited Algeria. Standing on an Algiers balcony with his commanding general Salan and the hawkish Soustelle, he addressed a crowd very much like the one that set the coup in motion weeks before. Introduced amid oceanic cries “long live Algérie Française,” he replied, famously, “Je vous ai compris”—“I have understood you.” He would later write that those words, “seemingly spontaneous but in reality carefully calculated” would fire the crowd without committing him to any further action. In the same speech, he spoke of “ten million French citizens of Algeria” who would decide their own destiny. Already he was using a formulation too liberal in its implications for any French politician in power to have uttered before. Then came a nearly heretical reference to the courage of the FLN guerillas. Their struggle, he said, “I personally recognize is courageous … however cruel and fratricidal.” Before the cheering stopped, some in the crowd must have wondered what exactly they were cheering for.

During his first year, de Gaulle set his generals to winning the war. France had by then completed the Morice Line, a complex of electrified fence and minefields that cut off the rebels from their sanctuaries in Tunisia and Morocco. Gen. Maurice Challe, the new commander of the French forces, developed tactics to keep the guerrillas on the run, and France had learned to induce more Algerians to fight alongside its own forces, the so-called harkis. By every statistical measure—insurgents killed, weapons captured, harkis recruited—the war was being won. All that was remained was for the guerrillas to seek surrender terms.

The army was not only winning, it was highly conscious that its honor was at stake. Soustelle explained it best, in a book published after he had broken with de Gaulle: the French army had made an oath to the Algerians and was bound by it. Every Algerian notable had asked the commanding officer of every village post “Are you leaving or staying?” If the notables refused to help the rebels, would the army protect them from reprisals? The army had always answered, “France remains and will remain,” Soustelle wrote. He concluded, “So don’t let anyone say that in committing themselves the officers committed only themselves. It was the whole army that made that oath, an oath that no one had the right or power to untie.” This powerfully emotive argument was impossible for many French officers to ignore and explains how perilous de Gaulle’s process of disentanglement would prove to be.

He began the task the following year. His cabinet was roughly evenly divided. His prime minister, longtime Gaullist Michel Debré, was an Algérie Française hawk. Even his closest ministers could only guess at de Gaulle’s own thinking. In September 1959, he spoke of Algerian “self-determination”—a process whereby the Algerian people would choose, through universal suffrage ballot, between independence, which he depicted as “cruel and impoverished,” a formal linking to France, or some less binding form of association. The FLN recognized that with these words, de Gaulle had acknowledged the legitimacy of their aim.

From that point forward, de Gaulle’s main adversary was the French Right. General Massu, the hero of the Battle of Algiers, denounced de Gaulle as a “man of the Left” in January 1960, and in the next two years de Gaulle faced down two coup attempts instigated by pied noirs allied with high-ranking dissident officers. He could not have squelched both without taking to the airwaves, appealing in a visceral and heartfelt language to the French people on television and to the army’s enlisted men, who heard him on transistor radios. Their loyalty, he intoned, was to France, not to their commanders. Both coups were close-run things; both could have easily succeeded, giving France a Franco-style military dictatorship and a slow bleed in Algeria that might have endured for a decade or more.

De Gaulle fashioned a referendum to legitimize the path of negotiations he had embarked upon, and by 1961, the French people overwhelmingly backed “the bill concerning self-determination.” He remained utterly, coldly realist: he did not want the Algerians to become part of France any more than the FLN wanted to. (In 1959, he privately remarked that under the full integration with France envisioned by some partisans of Algérie Française, his native village of Colombey-Les-Deux-Eglises would be turned into Colombey-Les-Deux-Mosquées.)

Rhetorically zigging and zagging, conscious always that he needed to maintain a certain baseline of military support to survive in power, de Gaulle moved toward negotiations with the FLN. After the collapse of the second coup attempt in 1961, the army and settler diehards of French Algeria formed their own terrorist organization, the Organisation Armée Secrète, and set out to assassinate de Gaulle while fomenting as much chaos as possible within Algeria to render the colony ungovernable. To what end? The best they could imagine was that some sort of apartheid solution could be created in Algeria. Some styled themselves a sort of pied-noir Hagganah. The broader strategy was never clear. But such was the rage against de Gaulle, and the number of officers who felt betrayed by him, that the OAS could carry out actions in both France and Algeria for over a year. They barely missed de Gaulle several times, and their terrorist “successes” in Algeria so poisoned the atmosphere that no settlers could remain there after independence. They brought terror to France as well. Jean Paul Sartre survived when a bomb meant for his apartment was placed on the wrong floor. André Malraux, the novelist who was de Gaulle’s culture minister, was a target as well, but a plastique intended for him maimed a four-year-old girl instead. By the end, OAS activities only increased the majority of Frenchmen who just wanted to be done with Algeria.

This Algeria fatigue was a sentiment de Gaulle nurtured, coaxing it along with his rhetoric. Asked at a press conference in 1961 whether the withdrawal of France from Algeria would open the colony to exploitation by the Soviet Union and the United States, he replied, with lofty formality, “I hope they both enjoy themselves there.” Or again, at a 1961 press conference, “Algeria costs us, it’s the least one can say, dearer than she brings in. … In sum, decolonization is in our interest, and consequently, our policy.”

At the final cabinet meeting, signing off on a negotiated settlement that essentially met all of the FLN demands (including the ceding of the disputed oil and gas rich Sahara), André Malraux declared that the end of the war marked a sort of liberation of France. Debré, overcome with emotion and still a fierce partisan of Algérie Française concurred, “It’s a victory over ourselves.” De Gaulle concluded, “It was vital to free France from a situation that had brought her so much misfortune.” No one in authority had any illusions that the agreements would be airtight in their application or that the new Algeria would be any better than a revolutionary totalitarian regime.

Freed of its colony, France quickly began to modernize its own economy (which grew at an amazing 6.8 percent in 1962 after the armistice). Algeria remained full of French teachers, doctors, and technicians. The French constructed a flattering narrative for themselves: they had “given” Algeria its independence because they wanted to, thus providing for the world a model for decolonization and modernization.

To the surprise of few, a darkness descended on Algeria. The first victims were the harkis, those who had served in the French army. Perhaps as many 100,000 were slaughtered, often with great sadism, being made to swallow their French medals before execution. Then the revolution turned on itself: Ben Bella, the country’s first president, spent most of the 1960s in an Algerian prison, as he had spent much of the 1950s in a French one. But France was done with it.

So how could the Algerian war not speak to us? Its example has long resonated in Israel, and many even hoped that Sharon—a successful military man of the Right—could do what no liberal Israeli leader could accomplish and withdraw Israel from the West Bank.

But now its lessons are dear to America as well as we search the horizon for a leader who can explain to the country—especially to the military and to the Republican Party—that its destiny doesn’t lie in the long-term occupation of Arab lands. The rhetoric that justifies the Iraq War as part of colossal battle against “Islamofascism” could be lifted almost directly from the French colonial intellectual slogans of the 1950s—and is no less self-deluding. To leave Vietnam, America needed a man of the Right, Richard Nixon. Today, when we need our own de Gaulle to achieve a “victory over ourselves,” we don’t even have a Nixon.