Jesus had most definitely had a nose job. Overlooking Lubango from a lofty plateau, this Rio-sized statue of Christ, his arms stretched wide in redemptive embrace, had been sacrilegiously strafed by an ungodly fighter pilot - even Jesus became a casualty of Angola's long and painful civil war.
Now, since 27 years of conflict that left 500,000 dead and tens of thousands displaced has finally ended, his shining alabaster-white face has been fully repaired - a beacon of hope.
With peace in 2002, rumours started circulating that Angola might be the next hot travel destination. After all, who'd have believed that just a decade ago Mozambique - the other erstwhile Portuguese colony similarly devastated by civil war - would now be the rising force of southern African tourism? Yet, while the Foreign Office doesn't exactly advise against travelling to Angola, it's hardly effusive, reporting "widespread poverty, social exclusion, and disease; a shattered infrastructure and millions of unexploded mines". Surely it was too early to consider holidaying in Angola?
But I was convinced I should go. I'd be in safe hands, joining the first group from the UK to visit Angola chaperoned by experienced guides. Our trailblazing tour would visit only the remote south-west, which saw little fighting and - most importantly - is landmine free. I was thrilled at the chance of being the first to experience somewhere rarely seen by the outside world.
From neighbouring Namibia we flew into Lubango, gateway to south-west Angola. As the war progressed, fighting became as much about controlling the country's abundant oilfields and diamond mines, and as the south-west provinces of Huila, Namibe and Cunene had neither, they were left alone. Not so the rest of Angola. Travel is more challenging in the heavily mined east, central highlands, and northern regions, where fighting was at its worst. In these areas, you'll need time, caution, a smattering of Portuguese and plenty of US dollars (post-war Angola is expensive).
Greeting us at Lubango airport, Ray Sakko warned there would be a few teething problems throughout our journey. Prophetic words indeed. Our hotel had been commandeered by five-star generals - not people to be messed with, so we relocated.
Lubango was pleasant although clearly suffering the war's shockwaves - particularly a lack of investment. Its Portuguese colonial architecture (including an extravagant art-deco cinema) was jaded, though tinted brilliant lilac by flowering jacarandas. Just a few overt symbols of conflict remained: several Soviet tanks rusted away near the city centre.
"The war was never serious down here although the uncertainty made life difficult," said Ray. "But the difference the last few years of peace has made with new businesses opening up and homes being rebuilt is amazing. Angola is definitely on the way up."
Yet this is a land soaked in unspoken tragedy. On our first evening we were taken to a local beauty spot. Tunda-Vala appeared heavenly. On the Lebbe Plateau a crack split the escarpment's edge way down to a bronzed plain, a giddying 750m below. Inside the fissure the waning sun inflamed the clinging vegetation. Ray said very little, not wanting, I'd thought, to spoil the moment. But later that night a stranger told me that, during wartime, captured UNITA combatants were shot and hurled into Tunda-Vala gorge.
We departed Lubango the next morning leaving the same craggy plateau via a concertina of hair-raising hairpins. The road eventually spilled onto a flat fertile plain of olive and citrus groves where roadside stalls sold chillies, ladyfinger bananas and muka, dried baobab fruit. Across much of Angola agriculture was reduced to subsistence farming during wartime as swathes of the countryside were callously mined.
Our trip was to involve a 2,000km drive, heading south along the Atlantic before veering inland to make an epic crossing of the Namib Desert along a rarely used route out towards Namibia. "The facilities will be mostly primitive and the roads terrible," warned Ray.
Angola's south-west Atlantic coastline is wild and largely undeveloped. At times the road south became an exhilarating beach drive, once pinching us into the surf by huge dune fields that continued south to become Namibia's Skeleton Coast. Not to be outdone, Angola's coast is similarly littered with broken shipwrecks beached like metallic cetaceans, their rusted shells teeming with wildlife. Abundant Cape fur seals dozed on the warm sands and we witnessed the start of the northern migration of pink flamingos.
One of the few creature comforts around was Ray and his father's isolated fishing lodge, 70km south of Namibe. Building Flamingo Lodge's palm-thatched cottages during wartime in the mid-90s was a leap of faith for the Cape Town-born Sakko family. Fortunately it didn't take too long for South African fishermen to take the bait and be reeled-in by the lure of record-breaking catches of rock cod and garrick.
"Still, it was tricky getting them here," Ray recalled with laughter. "Until 2002 tourists couldn't get visas so visitors applied for temporary work permits as plumbers and electricians. Immigration was very suspicious."
The following afternoon I hiked inland to an abandoned lighthouse. From its top the 360º panorama was jaw dropping - a biblical landscape of calamine flat-topped hills incised by wadis that coughed only dust into the cobalt Atlantic.
Cuban soldiers shared this very view during the war, using the bullet-punctured lighthouse's position to shell passing ships suspected of channelling weapons from South Africa to UNITA. Angola's conflict in the 1970s was shamelessly manipulated by the superpowers into a de facto Cold War: Cuba and the Soviet Union rallied behind the communist MPLA government while South Africa and the USA backed the rebels.
South of Flamingo Lodge lay the 80-million-year-old Namib Desert where the only conflict has been with the elements. It has been burnt, frazzled, windblown and cracked into virtual submission creating panoplies of ever-changing landscapes. Sometimes we drove through baked, featureless plains showered with quartz; sometimes shattered maroon escarpments streaked by blancmange-pink sediments resembling chunks of gateaux.
Everything oozed antiquity. We stopped along the way to marvel at Welwitschia mirablis, an oddball desert plant that looks like a charred and buckled satellite-dish sprouting decaying tentacles. "They look dead," I protested. "No, this one's 2,000 years old and still growing," insisted Ray, "about one millimetre each year."
The next afternoon we were again treading lightly, this time on a splintering escarpment where the outcrop's brittle crust peeled away like onion skins. "These rock engravings are 20,000 years old," explained our new guide Alvaro Raul Ferreira Baptista. "Ancient Bushmen would've used this plateau to spot prey and look out for lions."
The engravings exhibited slightly abstract patterns of concentric circles gouged into the granite. Spookily extraterrestrial, perhaps they were maps of the stars? Or more likely they had a meaning now lost to the sands of time.
Alvaro had taken us to them on an excursion from Omauha Lodge, which lay 165km inland from the coast. His wooden cabanas are the Angolan Namib's only lodge, tranquilly located in the lee of a bulbous bronze kopje (small rocky outcrop) on a 50 sq km ranch of semi-desert scrub. Most of his visitors are vacationing oilmen from Angola's Atlantic rigs.
Alvaro did well out of the war. While agricultural production stalled he grew and supplied fresh vegetables to the capital Luanda. Yet life wasn't without hazards. "I had a farm up north but it became dangerous as UNITA guerrillas came closer. Some nights we slept in the bush for safety and eventually we fled south," he explained. Savimbi's fighters were an instrument of fear, terrorising Angola's countryside for decades.
Now Alvaro's dream is to restock his ranch with wildlife. Pre-war Angola was one of the finest places in Africa to see animals. "I saw lions, 80 elephants and 1,000 zebra here," he boasted. "But most of the animals were shot for food during the war and the last time I saw a rhino was in 1981 - they were poached for their horns to be sold in Namibia."
You can still see leopard and cheetah on Alvaro's ranch and he is buying in wildlife from Namibia, but it's expensive. "One Burchell's zebra alone costs US$3,000," he sighed.
A few days later, as we drove through the 16,000 sq km Iona National Park, I could only imagine how sensational this vast tract of mopane and mimosa veldt would've been when full of game. Nature still threw us a few titbits - springbok, ostrich and several imperious oryx - but it felt strangely empty. Restocking game is currently a low priority in Angola although recently an elephant herd was translocated from Botswana into north-west Kissama National Park - times are a-changing.
South-east of Iona we continued towards Namibia on a rugged four-day haul across a horizon-busting expanse of savannah in the Cunene Province. We stopped only to camp at night under starry skies and to rustle up a braai (barbecue) on deadwood fires.
Despite the wearying travelling, this part of our journey was a revelation. The Cunene River region harbours many semi-nomadic tribes isolated by Angola's civil war and rarely seen - in all, about 90 ethnic groups are scattered across Angola. The people of Cunene are largely Bantu-speaking tribes of a larger grouping known as Mbundu, but with neither the territory nor the mineral resources the warring factions craved they were left alone. People-watching has never been so good.
Our first meeting with one of Angola's forgotten tribes was an intimate one. We were led into the thorny savannah by a dozen lean tribesmen wearing little more than loin cloths and carrying heavy staffs, their front two incisors filed into a v-shaped notch revealing a triangular gap whenever they smiled. "They are Mucucuroca," said Ray, although he confessed knowing little about them.
They were escorting us to a wedding where, under a spreading acacia, the bride's father had slaughtered a cow - a ritual to launch three days of festivities. Cauldrons of slithery intestines and bovine blood bubbled away on a cinder hearth - I prayed we wouldn't be invited for dinner. Around us men danced, whirling like dervishes while watched by unmarried girls sporting stunning box-shaped headdresses worn until their fathers' death.
The Mucucuroca's teeth filing is a remarkable cultural hangover dating back to slavery. From 1575 onwards, Portuguese slavers shipped Angolans in shameful quantities to Brazil. As slaves were partly valued by the quality of their teeth the local tribes took to despoiling theirs. The practice still remains today, centuries after abolition.
After a juddering day's drive across the stegosaurus-armoured Sierra Moimba we were delivered into the lands of the legendary Himba.
My first vision of the Himba tribe wandering across the dry savannah plains was completely unforgettable. Our first encounter was with a small group of Himba women - we were transfixed by their beauty and elegance. Even in such inhospitable terrain the women spend hours each day beautifying themselves: colouring their bodies in a butterfat and ochre cream, leaving their skin with a permanent reddish hue. Heavily adorned in jewellery, their mud-caked dreadlocks ended in frizzy cheerleader pom-poms.
Found both sides of the Cunene River frontier, there are concerns that in Namibia the Himba's lifestyle is changing too fast as tourist interest grows. Yet Angola's Himba remain remote, said to pursue an existence unbroken in its simplicity since the Iron Age. We later passed a Himba camp, draped with their cocoa-brown clothes; their snarling hounds ensured we left them alone.
Finally we arrived at another tribal home, a Mucuwana village near to Oncocua. It was partly ringed by upright logs sharpened like pencils - the sort of stockade I'd only ever seen in Tarzan films. The tribal elder, Jambali, invited us to a daylong celebration of the tribal elders. The party was an intoxicating medly of singing and clapping - the Mucuwana dance. The women were again dazzling, but different, with multicoloured braids, bead corsets around their waists and curiously Teutonic-looking iron crosses dangling down their backs.
It was here I sensed the paradox of Angola's war: fearful destruction, yet in some places preservation of a cultural landscape that has been lost across much of Africa. The country will take many years to heal, and longer to shed international notoriety. Yet at that moment, as the Mucuwana danced and Jambali reappeared with his collection of spears, I felt I was seeing Africa through the eyes of Livingstone.
Get the very best of Wanderlust by signing up to our newsletters, full of travel inspiration, fun quizzes, exciting competitions and exclusive offers.