It was the strangest journey of my life and it always will be. I was looking for fictional characters I had invented, in a country I had never visited. The distant town of my imagination was Bukavu in Eastern Congo, known formerly as Costermansville and built in the early twentieth century by Belgian colonialists. It stands at the southern end of Lake Kivu, at 4,800 feet the highest and coolest of all Africa's Great Lakes. I had written my novel in a period when for personal reasons I had felt unable to leave England. Now, too late if my previous books were anything to go by, I was about to check its people and places against the reality.

But the novel isn't really set in Congo at all–or so I had almost persuaded myself by the time I began my journey. It's a romantic satire, for heaven's sake, written with both feet firmly off the ground. It's about Tony Blair's England, and good old-fashioned colonial exploitation, and political hypocrisy and shameless public lies, and other scores I had to settle. It's about the quest for identity in our multiethnic society, and New Labour's assault on our civil liberties, and a bunch of other similarly lofty themes. Congo is just backcloth, an abstraction, a symbol of perpetual colonial exploitation, slaughter, famine and disorder. To meet it face to face would only violate the delicate illusion!–or so I had tried to believe.

The only problem was that, well before I had added the last full stop to the first draft, Congo had become the elephant in my drawing room, and no amount of literary sophistry was going to make it disappear. My central character was the son of an erring Irish missionary and a Congolese headman's daughter. He had been dragged up in a bleak English boarding school, and he and I could get along fine. I had no quarrel with him. But when it came to my three Congolese warlords, each one some sort of standard-bearer of the militia or social faction that had spawned him, I had doubts. Neither my researches, nor my furtive lunches with Congolese expatriates, had reassured me that these characters could survive in the real world. If my visit to Bukavu did not deliver their likely counterparts–by which I mean, verify their attitudes and beliefs–I might be forced to look for other ways to tell the story, such as writing it again from scratch.

In Belgian colonial memory, as in my novelist's fantasy, Bukavu was a lost paradise, a misted Shangri-La of wide, bougainvillea-laden streets and lakeside villas with lush gardens sloping to the shore. The province of South Kivu was to Central Africa what biblical Palestine was to Arabia. The volcanic soil of the surrounding hillsides was so fertile, the climate so benign, that there was scarcely a fruit, flower or vegetable that didn't thrive there. But Eastern Congo has like every paradise a fatal flaw: It is a natural treasure chest of gold, diamonds, cassiterite and now coltan and uranium, which for centuries has lured every known species of human predator to its misted hills and jungles, from freebooting Rwandan militias to suited corporate carpetbaggers with nice manners and fat checkbooks and shiny offices in London, Houston, St. Petersburg and Beijing.

Ever since the late 1960s, Bukavu has suffered catastrophe after disaster. In the wake of the Rwandan genocide that hand-killed almost a million people in a hundred days, the town found itself in the front line of the refugee crisis. Hutu insurgents who had fled across the border from Rwanda used Bukavu as one of their two main bases from which to attack the Tutsi-dominated revolutionary government that had ousted them and seized power in Kigali. Goma, at the northern tip of the lake, was the second. The Tutsis retaliated in what became known as the First Congo War, and Bukavu took the brunt. The town barely had time to draw breath before the Second Congo War struck. And in June 2004, Bukavu fell into the hands of one General Nkunda, who invited his men to do with it what they pleased for three days. The town was sacked, and scores of women were raped.

I had also read that the Roman Catholic cathedral that dominates the town is called Our Lady of Peace.

There were three of us in the car by the time our Rwandan driver took the winding hill road from Kigali and headed toward the Congolese border four hours' drive away. The Foreign Office had advised us not to go, but for my two traveling companions such warnings had about as much impact as a footnote in a backpackers' guide. Michela Wrong had spent twelve years reporting on the African continent. She had covered post-genocide Rwanda for Reuters and the BBC and had written a seminal book, In the Footsteps of Mr. Kurtz, about Congo's recent history. Jason Stearns, at 29 a senior analyst with the International Crisis Group, had served three years in Bukavu as a political adviser to the United Nations. He spoke immaculate French, Swahili and an unknown number of the more obscure African languages and was widely held to be one of the West's leading authorities on Congo.

Both had plowed through an early draft of my novel, forgiven my trespasses and offered advice. Both knew the kind of players I needed to meet, and the locations I needed to see. Both had their professional agendas but agreed to coincide their trips with mine. It was April. On July 30–but the date remained uncertain–the Democratic Republic of Congo was proposing to hold its first multiparty election in forty years at a cost of nearly $500 million, $400 million of them from the West. There was gathering nervousness about the outcome. For my companions this made it the perfect time to go, as it did for me, since my novel was set in the run-up to the same elections. My only problem was: Had I left it too late for my warlords?

Well before we reached the Congolese border, my imagined world had been changing before my eyes. The Hotel Mille Collines in Kigali, alias the Hotel Rwanda, where we had stayed the night, had an air of oppressive normality. I looked in vain for a commemorative photograph of the actor Don Cheadle, or his alter ego Paul Rusesabagina, the hotel manager who in 1994 had turned the Mille Collines into a secret refuge for Tutsis in terror of the panga and the gun. But that story, in the mind of the revolutionary party still in power, is no longer operative. The genocide, according to the prevailing political correctness, produced bigger and better heroes who were not darlings of the Western media. Ten minutes into Rwanda with your eyes open, you know that the Tutsi-led government runs a very tight ship indeed.

From the windows of our car as we wove toward Bukavu, we glimpsed Rwandan justice at work. In tailored meadows that would not have been out of place in a Swiss valley, villagers crouched in rings like summer schoolchildren. At their center, in place of teachers, men in prison pink gesticulated or hung their heads. To break the backlog of suspected génocidaires awaiting trial, Kigali has reinstated traditional village courts. Anyone may accuse, anyone may defend. Only judges are appointed by the government.

An hour short of the Congolese border we turned off the road and climbed a hill in order to take a look at a few of the génocidaires' victims. A former secondary school looked down on lovingly tended valleys. The curator, himself an improbable survivor, led us from one classroom to another. The dead–hundreds, of them, whole families, tricked into assembling for their own protection–had been laid out in fours and sixes on wooden pallets and coated with what looked like congealed flour and water. A lady with a face mask and bucket was giving them an extra coat. Many of the dead were children. In a country where farmers do their own slaughtering, the technique had come naturally: First cut the tendons, then take your time. Hands, arms and feet were stored separately in baskets. Torn clothing, brown with blood and mostly children's sizes, hung from the eaves of a cavernous assembly hall.

How had so many normally peaceable people been dragooned into becoming assassins at the drop of a hat? Answer: by a few bad men seizing the moment. By faking the evidence. By exploiting traditional resentments. By lies repeated over the radio. By persuading the Hutus that they themselves were about to be slaughtered by their Tutsi neighbors. Hermann Göring at his Nuremberg trial had the recipe off pat:

''Naturally, the common people don't want war…but after all it's the leaders of the country who determine the policy, and it's always a simple matter to drag the people along…. All you have to do is tell them they're being attacked and denounce the pacifists for lack of patriotism…. It works the same in every country.'' And we know it still does.

Would I, as a Westerner, have felt easier if the murderers had used Zyklon B to do their work? Or dropped 15,000-pound "Daisy Cutter" bombs from two miles up?

''So when will you bury them?'' we asked.

''When they have done their work,'' was the reply.

These dead have no one to name them, no one to mourn or bury them. The mourners too are dead. So the bodies will be left on show for a while, to silence the doubters and deniers.

Rwandan troops in green, US-style uniforms have appeared along the roadside. The Congolese frontier post is a dilapidated shed on the other side of an iron bridge across an outlet of the Ruzizi River. A cluster of female officials frown over our passports and vaccination certificates, shake their heads and confer. The more chaotic a country, the more intractable its bureaucracy. But we have Jason. An interior door bangs open, joyous cries are exchanged, Jason disappears. To peals of congratulatory laughter, our documents are returned to us. We bid farewell to the perfect tarmac of Rwanda and for five minutes lurch over giant potholes of red Kivu mud to our hotel.

In every trouble spot I have cautiously visited, there has always been one watering hole where, as if by secret rite, hacks, spies, aid workers and carpetbaggers converge. In Saigon, it was the Continental; in Phnom Penh, the Pnom; in Vientiane, the Constellation; in Beirut, the Commodore; and here in Bukavu it's the Orchid, a gated, low-built lakeside colonial villa surrounded by discreet cabins. The owner is a worldly wise colon who would have bled to death in one of Kivu's wars had not his late brother smuggled him to safety. In a corner of the dining room sits a German lady of a certain age who talks wistfully to strangers of the days when Bukavu was all white, and she could drive her Alfa Romeo at sixty miles an hour down the boulevard.

Next morning we retrace her route, but not at her speed. The boulevard is still wide and straight but, like every street in Bukavu, pitted by red rainwater gushing off the surrounding mountains. The houses are fallen gems of Art Nouveau metro-land, with rounded corners, long windows and porches like cinema organs. Where there are new buildings, the same style is replicated today. The town itself is built on five peninsulas, ''a green hand dipped in the lake," as it is locally described. The largest and once the most fashionable is La Botte, where Mobutu kept one of his many residences. According to the soldiers who barred our entry, the same villa was being refurbished for the new president, Joseph Kabila, Kivu-born son of the Maoist revolutionary and wheeler-dealer who in 1997 drove Mobutu from power and four years later was murdered by his own bodyguard. A steamy haze hangs over the lake for most of the day. The border with Rwanda splits it longways. The toe of La Botte tips provocatively eastward. The fish are very small. The lake's monster is called mamba mutu, half-woman and half-crocodile. What she likes best is eating human brains.

We enter a Roman Catholic seminary. Its windowless brick walls are unlike anything around them in the street. Behind them lies a world of tranquil gardens, television dishes, guest rooms, conference rooms, computers, libraries and mute servants. In the canteen an old white priest in jeans shuffles to the coffee urn, gives us a long, unearthly stare and goes his way. He suffered greatly but survived, our host explains, and laments how his fellow African priests are at risk from penitents who confess their ethnic hatreds too eloquently. Once inflamed, they are capable of becoming the worst extremists of them all. Thus in Rwanda, priests were known to summon all the Tutsis in their parish to the church, which was then torched or bulldozed with the priests' connivance.

My first warlord, Thomas, is about as far removed from my expectation as he could decently be. He is tall and elegantly dressed, and receives us with diplomatic grace. His house, guarded by sentries with semiautomatic rifles, is spacious and representational. A plasma television screen plays silent football while we talk. He speaks for the Banyamulenge, and his people have been fighting wars in Congo pretty well nonstop since 1966, but his own war was spent in South Africa, lobbying for their cause. The Banyamulenge, I had read, are pastoralists originally from Rwanda who over the last couple of hundred years have settled the high plateaus of the Mulenge mountains of South Kivu. Feared for their battle skills and reclusiveness, and hated for their supposed affinity with Rwanda, they are the first to be pilloried in times of discontent. Would the upcoming elections make things any better for them? we asked. His reply was not encouraging. The losers will say the vote was rigged, and they'll be right. The winner will take all, because why else win? Candidates are vying to demonstrate their pro-Congolese, anti-Rwandan credentials, so it will be open season on the Banyamulenge.

Thomas was similarly unimpressed by Kinshasa's efforts to incorporate Congo's many armed groups into one national army: ''We have many men who have joined and then defected to the mountains. In the army they kill us and insult us, although we have fought many battles for them.''

There was a chink of hope, he conceded. The Mai Mai, who regard themselves as the keepers of a Congo free of all ''invaders'' and ''foreigners''–including the Banyamulenge–are also learning the high price that must be paid to become a soldier of Kinshasa. ''Maybe as the Mai Mai learn to mistrust Kinshasa, they will draw closer to us.''

Afterward, I ask Jason whether Thomas was right to be gloomy about the forthcoming elections. By and large, thought Jason, he was. Elections were only one trapping of a democratic system. Without a Parliament, courts or an administration, they merely decided who got to rip off the country next. Thirty percent of Congolese lived on one meal a day. Eighty percent earned less than a dollar a day. The losers had guns, and would very probably use them to contest the outcome. And yes, another Congolese war could follow. Next day we met a colonel of Mai Mai, the largest and most notorious of Congo's many armed militias.

Like Thomas, the colonel is immaculately turned out. His Kinshasa-issue khaki drills are ironed and pressed, his badges of rank glisten in the midday sun.

We are sitting in an open-air cafe. From a sandbagged emplacement across the road, blue-helmeted Pakistani UN troops watch us over their gun barrels. The colonel fidgets a lot, perhaps in embarrassment. Two cellphones lie before him. His heavy French is rich in extraneous additives. Sometimes his language and beliefs seem a bit of a puzzle to him, as if he wants a different role in life but has been landed with this one. Like their forebears the Simba, the Mai Mai possess magical powers–dawa–which enable them to turn flying bullets into water.

''The Mai Mai are a force created by our ancestors. There are races in my country that do not deserve to be here. We fight them because we fear they will claim our sacred Congolese land. No government in Kinshasa can be trusted to do this; therefore, we do it ourselves. When Mobutu's power failed, we stood in the breach with our pangas, bows and arrows. Our dawa is our shield. When you are face to face with an AK-47 that is firing straight at you and nothing happens, you know our dawa is authentic.''

In that case, we ask, how do the Mai Mai explain their dead and wounded?

''If one of our warriors is struck down, it is because he is a thief or a rapist or has disobeyed our rituals or was harboring bad thoughts about a comrade when he went into battle. Our dead are our sinners. We let our witch doctors bury them without ceremony.'' And the Banyamulenge? we ask. ''They can remain in Congo if they accept Congolese law. If they don't, we shall kill them.''

Venting his anger against Kinshasa, however, the colonel comes significantly close to sharing the sentiments expressed by Thomas the night before: ''The Mai Mai have been neglected and marginalized. Kinshasa forgets too soon that we fought for them and saved their arses. When Mai Mai fighters join Kinshasa's army we become kings without kingdoms. They don't pay us and don't listen to us. As soldiers we are not allowed to vote. Better we return to the bush and look after ourselves.'' And as a parting question of us: ''How much does a computer cost?''

In my novel, I have sketched in an armed attack on Bukavu airport. We are about to set off to inspect the reality when we learn that the center of town is blocked by demonstrators and burning tires. It seems that a man mortgaged his house for $400 in order to buy his wife a medical operation. When Kinshasa's unpaid soldiers heard about it, they raided his house, killed him and stole the money. Angry neighbors seized the soldiers, but their comrades sent reinforcements to get them back. A 15-year-old girl was shot dead and the crowd rioted. In our five nights in Bukavu, there were two riots.

After a tortuous drive through uneven back streets we reach the Goma road and drive northward along Lake Kivu's western shore. The airport is under the joint UN protection of Indian and Uruguayan troops. Not long ago, the Rwandans took the place over and remained there for several months without anybody interfering. The Uruguayan soldiers, who are not allowed into town, give us an excellent lunch and urge us to come back for a real party soon. ''What would you do,'' I ask an officer, ''if the airport came under surprise attack?'' His right fist clenches and shoots forward as his left hand closes over his forearm. ''Vamos,'' he replies.

The discothèque is my last and most affecting memory of Bukavu. In my novel, it is owned by the French-educated heir to an East Congolese trading fortune. He is a warlord of a sort, but his real power base is Bukavu's young intellectuals and businessmen. And here they are. There is a curfew and the town is quiet. A bit of rain is falling. I recall no winking signs or bulky men checking us at the entrance, just a gray row of little Art Deco buildings disappearing into the dark, and a rope bannister descending a dimly lit stone staircase. We grope our way down. Music and strobe lights engulf us. Yells of ''Jason!'' as he vanishes under a sea of welcoming black arms.

The Congolese, I had been told, know better than anybody how to have fun, and here at last they are having it. Away from the dance floor, a game of pool is running so I join the lookers-on. Round the table, deathly silence attends every shot. The last ball goes down. To hoots of joy, the victor is swept off his feet and carted in triumph round the room. At the bar, beautiful girls chatter and laugh. At our table, while I listen to somebody's views on Voltaire–or was it Proust?–Michela is politely discouraging a drunk. Jason has joined the men on the dance floor. I will leave him with the last word: ''For all Congo's troubles, you meet fewer depressed guys on the streets of Bukavu than you do in New York.''

Would I have written the same novel if I'd gone to Congo earlier? I wonder whether I would have written a novel at all. The reality of the place is so overwhelming that stories about it seem almost an irrelevance. But then I wasn't really writing about Congo, was I? It was all those other things. Congo was just backcloth.