On a shelf in front of me is a collection of shrivelled heads, each the size of a petanque ball, staring me directly in the eye. The mouths look twisted in an expression of pain. The air is thick with a cold and devastating air. I'm in a dark wooden 'man's hut' in Papua New Guinea's forested Highlands region and it seems I'm in a fantasy.

But then Papua New Guinea is something of a fantasy. Sitting off the northern tip of Australia, PNG is a country of 850 languages, diverse and remote tribes and rich tropical environments, with no fewer than 700 different species of birds scattered across jungles, beaches and volcanoes. It is also savage and wild, they say; a country not to be trifled with.

When I board the 300-mile flight north from Port Moreseby to the Highlands, which carries a reputation as the wildest province of this wild country, it is with some nervous excitement. What, I wonder, will I find here? Cannibals, like the taxi driver in Port Moresby warned me? Warring headhunters? King Kong himself? Touching down in Mount Hagen, the rambling shambling capital of the Highlands, some of my fears are realised. The people are grim-faced. Men carry metre-long machetes, their mouths stained a ghastly crimson. There's a rough sense of violence in the air. And if this is the city what will the tribal lands be like?

Well, funnily enough, an hour out of Mount Hagen, where these lands start, the grisly veil is lifted. All of a sudden everything is pretty, ordered and bucolic. There are coffee plants, sweet potato and peanut crops flourishing by the roadside. The bushes drip with red heliconia plants, looking like Chinese fireworks. Each person I pass stops and waves. Those stony, basilisk faces are suddenly replaced by dimpling smiles. My driver, Joe, beeps and waves at them in return. "In Port Moresby they say you're angry folk," I tell him.

"The people from Port Moresby have never been up here," he replies with a casual shrug. Swept along on a cool breeze to my destination, Rondon Ridge, as the sun sets high above the Wahgi valley, I begin to think this isn't savage at all. Well, they do say city life isn't all that.

The bushes drip with red heliconia plants that look like Chinese fireworks. Each person I pass stops and waves

Rondon Ridge is operated by Trans Nuigini Tours, which has built its hotels on some of the primest locations in PNG. Stepping out of my minibus I'm expecting some kind of modest self-help accommodation but the 'room' they've put me in – a huge three-floor affair with high windows facing out across the valley – is anything but. Looking out of the windows as night falls, I see a storm illuminate the valley. Flashes of silver crack the backdrop of a jungle spreading out for miles below. I can only observe and let my jaw drop. PNG surprises. A lot.

The Wahgi valley was only discovered by the outside world in 1934, when three Australian brothers came prospecting for gold. But there's this continued sense of timelessness about this place; a joyous primitivism with the gods of nature all around you.

The next day, in bright tropical sunshine, I'm off to visit a local village in the valley where I'm going to watch a 'sing-sing', which is, indeed, a ceremony of worship to the Gods and ancestors. The village is pretty, with tended gardens where lush plants and bright, blooming flowers house cobwebs containing spiders as big as your head. Around the first turn I'm confronted by a fierce old man with a pierced septum, who's wearing a grass skirt and holding a bow and arrow, which he has cocked right at my eye. Noting the look of panic in my face he lowers the weapon. Actually, he doesn't want to shoot me, even though that serrated arrow could take out my liver. It's a warrior display like they would've put on in the old days – though I think he may have enjoyed the expression of gutlessness on my face. I'm learning that the people of PNG are full of dark humour.

The sing-sing I'm here to watch is that of the famed Asaro mudmen. A song starts and bushes begin shaking. From these bushes creeping men appear, smeared in white clay and wearing oversized ghoulish mud helmets and carrying long, sharp bamboo stick fingers ,which they twitch in the air with a click and a clack. OK, well this is scary. But it's meant to be. The sing-sing represents the spirits of dead ancestors haunting their enemies. It's a window into the history of an ancient culture.

Though I'm fifty-odd years too late to be a proper explorer I can see why PNG still holds a fascination for adventurers, with all its myth and remote tribes and ageless culture. But with pipelines and mining crews gathering around, how long will this last? I'm told that as a tourist I help keep these local traditions alive by getting the folk out and practising. But I'd rather be an adventurer.

Speaking of which, north of the Highlands is the East Sepik province, 43,000 square kilometres – about twice the size of Wales – of thickly forested, mountain-blocked land, where explorer Benedict Allen went missing while looking for the remote Yaifo tribe last year. When I arrive from my temperate Highland valley I find the world changed to tropical fire. My new digs, Karawari Lodge, sit high up on a ridge in the jungle, the brainchild of an Australian police chief in the 1970s, who stuffed it full of colonial relics like the dark wooden statues showing off colossal priapic salutes that litter the place.

Down below the lodge, the Karawari river winds like an oily snake. Chugging along it the next day in a steel-bottomed boat, the wild sugar cane and pit pit grass growing by the banks and white herons and multicoloured lorikeets gliding by, I realise how isolated we are. It's all so still and eerie like Conrad's African heart of darkness. Then the captain switches off the motor and I hear a strange noise – a hollow echo all around us like a metallic howl. The skipper says it is the fish moving under the boat but it feels more ominous to me. A great, mystical presence in the water. Or maybe I'm just a little pickled by the sun.

While they are only separated by a few hundred miles, the tribes along the river are as different to the Highlanders as the Highlanders are to Port Moresbians and Port Moresbians are to PNG's islanders. The country is, indeed, a unique melting pot of races – Melanesians mixed with Micronesians, Polynesians and Negritos, Malays, Aboriginals, Teutonics – split by tribes, clans and family that keep them unique and apart.

Papua New Guinea is a mecca for bird lovers

Papua New Guinea is a mecca for bird lovers

David Kirkland

In this part of the country the food – sago starch taken from the pith of sago palms and fish – customs, language and look is distinct. And they have their own ceremonies and souvenirs – like those shrunken heads which I see in a smoky hut – that they keep as a reminders of their savage past. But cutting through the myths, this place is nothing like the savage land depicted in Western tales. Yes, there are inter-tribal feuds, but there are more 'I lived with a Papuan tribe and got caught in tribal warfare' stories out there than there are wars. All I find by the river is curiosity and warmth.

PNG also has another trick up its sleeve: birds. The country has 38 of the world's 43 birds of paradise, the most concentrated diversity in the world. These birds are so rare that explorers believed they lived in the heavens and were only seen once they had dropped dead onto the ground. So far I've encountered none; not a single tail feather. But they tell me that I have a good chance of finding them in Ambua Lodge in the Highland rainforest near Tari. I'm told I should seek out Joseph there. He is, they say, the Mozart of ornithologists. He's helped people like Attenborough find them. His nickname is 'God.'

So here I am in Ambua, it's six am, raining and we—myself and my two globetrotting companions Michael and Ali— are waiting for Joseph. My heart is thumping. In my mind is a picture of Marlon Brando in Apocalypse Now, all groaning sighs and shadows and godlike charisma. And then I see this purple cagoule and drooping green beanie emerge from the rain. It's Joseph. He does not look happy. In fact his face is thunderous in the weather. The rain that bears down seems to have formed an unhappy microclimate around his beanie.

They say he's the Mozart of ornithologists. He's helped people like Attenborough find them. His nickname is God

"Joseph, I've heard all about you," I cry, bounding up to him like an excited puppy. "To see the birds!"

"No chance in this rain," he mutters and walks off.

OK. We get on the bus, which slowly tootles up a hill with four inside, Joseph sitting near the front, motionless. I'm trying to get a sign but eliciting any information from this rock of phlegmatism is impossible. He is dyspeptic. I am dismayed. And, of course, there are no birds outside. Just rain, rain, rain.

We carry on but there's nothing to see and so eventually the bus turns and begins driving back down the hill. A mile down, we pass another bus – full of a load of freshly arrived Americans – stopped by the roadside, with a chipper guide who's pointing to the jungle.

"Won't see anything in this rain," answers Joseph before I've even got the question out.

Finding no birds except a pigeon, I'm pretty depressed. Is this really the legendary Joseph? The one they said would find us the birds? Where's the man's heart? Even as I'm thinking this Joseph has unexpectedly called for the driver to stop. He's peering into a canopy of trees by the roadside.

"In there," he points. "Come."

Unhesitatingly we follow as Joseph bounds into the thickness. Suddenly he's all catlike, hopping through bushes and trees, down one turn and the next, weaving like a panther. He raises his hand for quiet.

"There," he whispers, handing me his binoculars. "In the tree."

"Where?"

"There, you fool!" He points up.

My eyes narrow and suddenly I see it – a bird of paradise! Not just any bird of paradise, it's only the bloody King of Saxony, the most magnificent of them all. And it's doing a display.

Need to know

Get to PNG on Air Niugini which flies daily from Singapore to Port Moresby. Wildlife Worldwide offers a twelve-day tour package around the Highlands and East Sepik provinces for £7,595 pp which includes charter flights and lodge accommodation.

"And there." Joseph shoots his arm to another tree. "Ribbontail."

Cascading white tail plumes, dancing and flirting in the branches, it's a second bird of paradise. And there are more – tiger parrots, black sicklebills, astrapia, dropped down from the heavens, indeed. The trees are teeming with them as if Joseph has orchestrated the whole thing. And suddenly I see the poet's soul behind the facade. The genius behind the wall. And that's PNG all over. A miraculous face and an even deeper, smiling soul.