On an island in the remote far reaches of the Northern Territory is a journey not only through a remarkably wild and dangerous natural world, but through thousands of years of human history. Welcome to Groote Eylandt.

“I reckon someone might’ve gone through the fibre optics cable on their tractor." It serves me right, I suppose, for asking the big, bearded bloke pulling beers behind the bar why I can’t get emails on my iPhone.

The men all round him – knocking back ice-cold stubbies after a long day trolling for game fish – hardly look the Facebook type.

Tall tales aren’t for mates a thousand kilometres away; they’re for the blokes beside you. The ones that slap your back and scream advice as you pull the big one in. The type who’ll back up your bullshit stories, because they’ll sure as hell want you to back up theirs.

“The same thing happened last year." Oh, the bartender’s actually serious: someone really did run over the internet on their tractor. “All of East Arnhem Land lost their signal for a week."

The sun’s setting outside, a splurge of orange and red so profound someone should be selling tickets; though nobody, of course, can post a single shot.

Out in the mangroves and beside the rough sand beaches that skirt the Gulf of Carpentaria – just beyond the safety of my spot here on the deck of Groote Eylandt Lodge – the encroaching dark is full of creatures that would love to drag me down under all that blood-warm ocean.

There’s always been something about being in the Territory that makes me feel like I’m teetering on the edge of an abyss: that if I take one wrong step, it’s curtains for me.

To anyone who reckons it takes a safari in Africa to experience ultimate adventure in the wild, I’d counter: where else on the planet but the Northern Territory can you consider yourself an extreme traveller just sitting outside your room having a cup of tea in the morning?

I’ll be spending a week here, far from the bright lights of the capital, Darwin. Where I’m going – the largely unheralded Groote Eylandt, and the largely unreachable East Arnhem Land – few tourists ever venture, and so life goes on as it always has, and probably always will.

On Groote Eylandt, they keep saltwater crocs for pets. And why not?

The Territory’s the only place in the world where you’re allowed to; and dogs and cats have a habit of disappearing round these parts. Head ranger Adrian Hogg is cradling his pet crocodile in his arms like a newborn baby.

“They make great pets," he says, stroking its snout just above the teeth. “But they’re not for everybody. Just watch them, even when they’re little buggers, they bite and spin. They can strip your finger in a second flat."

All but 30 tourists a year who come to Groote Eylandt come to fish, this being one of the world’s premier game fishing destinations.

But the island’s newly appointed tourism co-ordinator, Nick Darby, is adamant there’s much more to do.

The roads on Groote Eylandt that don’t lead to the mine (Groote Eylandt produces a quarter of the world’s manganese) are all fiercely corrugated red dirt trails.

But they lead to places Nick’s only just discovering, often just days before I do (and where else on Earth does that happen?) He’s excited today; he’s taking me to an Aboriginal community on the other side of the island that he’s only just received permission to bring travellers to; I’ll be the very first guest there.

Groote Eylandt may well teem with waterfalls and many-millennia-old cave paintings, but Nick’s only just finding them.

Here at Umbakumba Aboriginal community, a tiny outback village sits beside a sea the exact same shade of blue as the sky; it’s so clear that I watch queen fish jump, and tiny slivers of bait fish chased by God-knows-what. An eagle ray leaps clean out of the water as I sit cross-legged on a tiny concrete jetty savouring my morning tea.

“There’s a croc that likes to sit out there on the reef line," Nick says, a reminder, if I needed one, that the Territory is no place for ocean swimmers.

We bash back across the red dusty trail and cool down in the shade of stringy barks.

I paddle in the clear, chilled waters of Leske Pools, watching blue-winged kingfishers flit from tree to tree. There could be death adders in the red sand beside me, but at least I’m safe for now from saltwater crocs.

Just around the corner, Nick surprises me with a picnic he’s set up on a sand bar in a billabong. I sit in a plastic chair nibbling cheese and sipping wine as a goanna shoves a yabby that it has fished from the water slowly down its throat.

There are Aboriginal cave paintings around these parts – plenty of them.

Nick reckons maybe only 50 outsiders have ever seen the ones he’s taking me to. They’re reached via a winding trail through black snake country, which takes me high above the gum trees below.

And there are many more sites yet on Groote Eylandt that will “blow my mind", but I can’t see them just yet. “No white man’s ever seen some of them," he says – rock chasms, secret canyons, green waterholes. No one sees anything around here without permission from the locals.

Back at the lodge, I walk next door to the Anindilyakwa Art Gallery where resident artist Alfred Lalara shows me a dash painting he’s just finished. When I ask its meaning, he looks shyly at a woman perusing the artwork across the room. “Not with her here," he says, so softly that I can barely hear him.

Others sure don’t mind telling me stories on Groote Eylandt. Like the one I’ll hear most nights about the prawn trawler captain who fought the mackerel boat mob; then when he rowed his tender off to lick his wounds, he capsized and no one ever found his body. When we drive past Groote Eylandt’s nine-hole golf course, Nick points at the second hole green.

“See that," he says, pointing at players ready to putt. “They don’t know there’s a big croc sitting below them looking up at them." The town here’s not much more than a rough grid of red soil and strangely resilient green grass that constitutes a footy field. There are mango trees and a row of fragrant frangipani, about all that separates suburbia from the cruelty of the outback.

In the evenings, I listen to the fishing mob warm up their tales, but when the light fades out entirely, I prefer the silence out here under the starriest skies I’ve seen. Beaming planets shine down at me, tiny stars glint and blinking stars shoot across the entire sky so slowly I can look away and still catch them. I fight the urge to watch it all lying on my back on the beach beside me.

I spend two more days on Groote Eylandt, but I long to go further into the Territory, beyond where any commercial airline can take me. In the Top End, if you really want to go bush, you’re going to need your own plane. And in the Territory, no plane’s more capable of getting you there than a Cessna 210.

“It’s the workhorse of the Territory," my pilot says, rubbing his hand affectionately across the wing of the Cessna flying us to Davidson’s Arnhemland Safaris’ lodge from Darwin.

The lodge is built within a land belonging exclusively to the local Indigenous people, set on 700 square kilometres of sacred land exclusively leased from the Amurdak people of East Arnhem Land.

East Arnhem Land is home to some the oldest peoples on Earth. And this morning, they got even older.

The paper I’m reading says anthropologists have discovered that Aboriginal people have lived in East Arnhem Land for 18,000 years more than the 47,000 they’d previously estimated: 65,000 years of continuous occupation. Imagine.

As we lift into the sky, keeping low over a landscape of red-brown sandstone escarpments, broken only by skinny, snaking rivers that flood come the wet season, making all I’ll be seeing totally unreachable, I try to comprehend thousands of generations of humans eking out a life down there below me.

Airports in East Arnhem Land come without security screening or cafes. They’re no more than a bumpy red track cut between gum trees and barely wide enough for a plane to land on.

We’re met by a bloke in a dusty LandCruiser, and driven just around the corner to the lodge.

Davidson’s Arnhemland  Safaris’ eco-lodge is as luxurious as it gets this far east of Darwin, though luxury in the Territory comes without Jacuzzis or gold-plated bathroom vanities: five-star round here is about exclusivity, and at Davidson’s there’s no one around you for 200 kilometres in any direction.

Locals have another measure for luxury in these parts too, it’s how cold your beer is. The further into the Top End you go, the harder it is to keep your beer cold.

The diesel they need to run the generator that keeps your drink chilled at Davidson’s has to come from Darwin, five or so hours’ drive down a dirt track through the bush. In the Wet, no truck’s got a hope in hell of making it through.

Ranger Luke Troup sits me down at the bar, before I leave the relative safety of our compound. “If you walk off into the bush around here you tend to perish," he says slowly. “And don’t get too complacent, salties [saltwater crocs] will walk long distances across floodplains, mostly at night, so don’t think fresh water in the Territory is safe."

We traverse tracks among monsoonal rainforest and past paperbark swamps in the back of an old modified LandCruiser (no one trusts anything but a LandCruiser in the Territory) until we reach sandstone escarpment country. Here valleys, overhangs and caves have been occupied by the Amurdak people for tens of thousands of years.

We climb a trail beneath a towering escarpment, until we reach an overhang on the cliff face. We squeeze through a tight gap while above us, an enormous serpent is painted at face level.

“This one they reckon goes back 20,000 years," Luke says casually. “I’ve had people from all over the world studying rock art and they reckon the rock art here’s better than anywhere. Lots of paintings round here, no anthropologist has ever seen. The Amurdak people don’t want them to. We only find out what they want to tell you, and, mate, they don’t tell you much."

Among the flowering grevillea in the cracks between the rocks, where 100-year-old kentia palms manage to make the outback look tropical, there’s an energy flowing right out of the earth. You don’t have to be cosmic to sense it either, you just have to open your eyes: all around me white, ochre, yellow and red rock drawings depict the last 50,000 years of human habitation on this planet.

Later, when I’ve let the heat drain from a Top End afternoon in the bar (bonding with local characters like veteran tour guide Seb Lord, who tells me he “won’t touch vegans" when he’s booking clientele), we take a slow boat ride up a creek lined by paperbarks, into a billabong dwarfed by towering escarpments.

Cormorants and brahminy kites circle the heavens above, staying clear of the thousands of magpie geese who scramble off towards the sunset (40,000 gather here each September). Saltwater crocs lurk in the shallows, only their prehistoric heads show above the surface, set in permanent sneers, their rows of incisors warning enough for any creature to keep its distance.

For the next three days I explore this place day and night; I’ll hit a five-metre croc in a five-metre runabout in the shallows of a narrow creek entrance, riding the wash as it thrashes about in protest. I’ll tiptoe through caves full of ancient bones, all that’s left of the people who once lived here (“they’ll be here till they break down to dust and go back to the earth," my guide tells me).

And in the quieter moments – afloat on a billabong with Champagne in hand as the colours of the sunset lend a delicacy to this place that makes me forget momentarily that I’m surrounded by crocs twice as long as me – I realise that there’s no limit to adventure in the Territory.

If we view human existence in Australia as a single day, non-Indigenous people’s time in Australia makes up a matter of minutes, whereas Indigenous people have been here since the crack of dawn. A visit to the Territory isn’t about where you go, it’s about the passage back through time you take – thousands and thousands of years – to the people who lived and died here so many times over, and the memory of them that lingers.

Groote Eylandt and Davidson’s Arnhem Land Safari’s details

Getting there: Qantas, Virgin and Jetstar fly to Darwin from Brisbane, Sydney and Melbourne. Airnorth fly to Groote Eylandt from Darwin.

Staying there: Stay at Groote Eylandt Lodge which can arrange all your tours, including cultural tours and fishing charters.

All meals and tours are included at Davidson’s ArnhemLand Lodge. The lodge can also organise air transfers.

For more information on Groote Eylandt, visit the Groote Eylandt section of the official Northern Territory website at northernterritory.com