Stretching across the northwest corner, the road from Darwin to Broome runs through one of the world’s last great wildernesses. Take a journey along this epic highway and into the history of Australia.

No more than five minutes out of Darwin, and the suburbs have already given way to outback. A shimmering highway runs straight into the distance until it is broken up by heat and a metallic blue sky. Dust is seeping into our four-wheel drive, settling on our supplies of drinking water and emergency snacks, our spare tyres and satellite phone. I can even taste it on my lips, dry and salty – the powdered essence of Australia.

Ahead of my companion Catherine and I stretches a journey through some of the wildest and most sparsely populated country on the planet. This is a land where there are areas larger than Ireland without a single town, where farmers lose dozens of cattle a year to crocodiles, and whole communities are cut off by flooding for months during the rainy season, known as 'the wet'. The Top End, as locals call this northern tip of Australia, is known for its characters: real 'Ozzie battlers', who came north to make their fortunes and never went south again. These are people to whom a fence ripped up by a wild buffalo, or a head-high flood, is as normal as a rush-hour traffic jam is to the rest of us.

The high rises of the city have been replaced with termite hills, some three metres high, which tower over the wattle trees. I gaze at the road that will take us from Darwin on the north coast to Broome in the west. It's a journey of hundreds of miles over tarmac and dirt tracks, and into the very fabric of Australia's past: a mere 150 years or so of 'whitefella' history, and the quiet millennia when the Top End belonged only to the Aborigines.

Kakadu National Park, 152 miles
Sitting on the warm sandstone at the top of Ubirr rock and peering over the edge to palm trees far below, I am dizzyingly aware that the scene before me has remained unchanged since prehistory. In the distance, the craggy lines of the Arnhem plateau stand out against the azure sky. Beneath it, stretching all the way to the feet of Ubirr, lies a huge and perfectly flat, lettuce-green flood plain, through which the lazy curves of the East Alligator River meander.

During the wet, water cascades off the plateau and submerges thousands of acres of the Top End, turning dozens of sandstone outcrops such as Ubirr into little islands. The temperatures rise to 45°C, with 100 per cent humidity, and there is little to be done but to sit the season out. For as long as 60,000 years - since humans first crossed into Australia - Aboriginal peoples have been gathering on this very rock during the rains, to take shelter in its nooks and crannies, to rest and talk.

We know this not only by the strange, shiny grey appearance of the sandstone - caused by centuries of polishing by human skin - but also by the fluent lines of Aboriginal art on the overhanging rock face beside me. Saratoga fish and pignosed turtles, complex depictions of myths, and simple handprints are layered on top of each other, the evidence of generations of storytellers and listeners. I hold up my hand and fit its shadow into Marlee Ranacher gets to work at Bullo River Station, preparing to brand her herd of cattle an ancient handprint. The beauty and immediacy of the paintings is striking enough, but seeing them here - where the descendants of the artists are still living, and practising many of the rituals and bush skills that these images refer to - makes the connection to the past seem much more tangible, as warm as touch itself.

We stay at the Kakadu Culture Camp, in tents beneath the woolly bark trees. As night falls we sit around the campfire and listen to the camp's owner, Jenny Hunter, talk about traditional Aboriginal bush skills. Jenny is half Bininj, the word for the indigenous people of Kakadu. 'If we want something,' she says, 'we just go out and get it from our supermarket - the bush. Everything we need is there. These green ants - they taste citrusy: good for colds. This paperbark tree, we call it 'the tree with a thousand uses'. We use the bark to wrap things up, or as oven gloves, to make canoes, or to cook food in.'

But times have changed, even in remote Kakadu. 'The old people like to eat bat and wild crocodile,' says Jenny, laughing. 'But it's too smelly for me! You start to smell like a bat yourself if you eat too much of the stuff. Our old people love it, but I'd rather not eat that stinky bat.'

Bullo River Station, 621 miles
Southwest of Kakadu, huge views of the Gregory National Park open up and there are more road trains than cars on the highway - rumbling juggernauts pulling double-decker cattle trucks, taking stock to market. 'Hurt me good' invites one, in an arc of steel letters over its cab.

We drive up to Bullo River Station in the late afternoon light, disturbing a flock of white corella birds and dozens of hopping wallabies on the way.

In the 1880s, the first cattle farmers rode into this part of East Kimberley, having driven their herds of shorthorn cattle all the way from Queensland, more than 600 miles away. Their epic struggles to make a living in the Top End were depicted in Baz Luhrmann's film Australia. For all its panning by the critics, the film seems like understated realism after a few days at Bullo. We drink beer late into the night around the barbecue, hearing stories of life on Bullo's half a million acres of virgin land (the same size as Luxembourg) - tales of discovering new pieces of rock art, fishing for barramundi, trapping crocodiles. 'There's a lot of variety,' remarks Franz Ranacher, who runs Bullo with his wife, Marlee. 'It's not like you're walking down the same city street every day.' The old stockman, Evan - bow-legged, leathery, courteous as a prince - tells me there's a muster on tomorrow. 'You can help with the sorting, if you'd care to.'

The station's 8,000 head of Brahman cattle live wild and are only mustered once or twice a year - no longer on horseback, but with helicopters and quad bikes. The next morning a herd of about 60 thunder down the airstrip, kicking up great clouds of dust, and we hurry to the pens. Marlee is already there - a short, smiling blonde woman who does the work of several men: branding and castrating, driving the heavy machinery to mend the roads, rounding up the cattle on her quad bike with a shotgun beside her. 'Marlee doesn't hesitate,' Evan says proudly. 'She'll shoot a dingo down in 30 seconds.'

The cattle must be sorted into different pens, according to whether they are ready for market or need branding. Those that have never been in the yard before are feisty, clanging their horns against the rails. Irish stockman Sean is forced to scramble up to the top rail, where he teeters like an acrobat as he tries to whip a furious young bull into the central hub. The rest of us stand back watching and roar with laughter. 'It's not a bad way to live,' says Marlee. 'Not a bad way at all.' Gibb River Road, 777 miles It's a drive of several hours from Bullo to the prosperous mining town of Kununurra, after which we turn off the tarmac onto the start of the Gibb River Road. It's little more than a gravel track, but it still forms the only route through the centre of the Kimberley - the gigantic, barely inhabited wilderness that forms the northwest corner of Australia. Closed during the wet, the 370 mile-long Gibb has a formidable reputation for challenging driving: its dozens of river crossings, many of them attended by hungry crocodiles, its slippery corrugations and its remoteness - with no mobile reception anywhere should you happen to slide off the road - can seem pretty daunting.

Yet once we hit the dirt and the Gibb is uncoiling in a thin red ribbon across the valley ahead of us, the road surface - and even the river crossings - soon cease to alarm. Other vehicles pass just often enough for us to feel confident, but not annoyed. The mighty boabs, known as upside-down trees, stretch their silverysmooth branches like elephant's trunks up to the sky, while a feather-trousered eagle rises slowly from the side of the road, and we are filled with exhilaration at it all.

The Kimberley has the wonderful capacity to surprise: its vast and arid landscapes will suddenly throw up a series of sandstone bluffs like crusader castles, or split open into delicious gorges with tumbling cascades and thermal pools fringed with palms. After hours of driving through the dust and heat, to plunge into a cool, green waterhole (having first checked for crocodiles, of course) feels unutterably luxurious - not a sensation I'd previously associated with this part of the world. We stop too often. The light fades as we drive towards Mount Elizabeth, wild donkeys peeping out at us behind the smooth and silvery ghost gum trees.

Mount Elizabeth Station, 990 miles
'Forty-one years ago I came up from Perth to work here,' Pat Lacey, Mount Elizabeth's owner, tells me at breakfast. 'Married the boss's son and stayed, although I didn't plan it that way. In those days the road was really rough. It was a nine-hour trip into town; we'd go twice a year.' She smiles. 'Of course, when my father-in-law Frank started keeping cattle up here in 1945, there was no road at all. Everything had to be flown in - such as building materials and diesel. They were only given six barrels of diesel per station, and once that was gone it was back on the horse!'

Before the Gibb River Road was built in the 1960s, the greatest challenge that faced cattle owners in these parts (even more so than at Bullo) was that of getting their stock to market, either to Derby at the western end of the road, or all the way up to Darwin. In Australia, Baz Luhrmann devoted the entire epic to the delivery of one herd from the Kimberley to Darwin. Yet for Frank Lacey and his mates, such journeys - driving hundreds of cattle on horseback over this craggy, spiky, snake and croc-infested terrain - were simply part of everyday life.

'Well, Frank even drove cattle over to Queensland,' says Pat. 'They were real heroes in those days. Once they started to build the road in the 1960s, it made running the stations out here easier. We send the cattle to market by lorry and they arrive with flesh on them - not skin and bone. Don't get me wrong - it's still over four hours to a shop, and then I get home and find I've forgotten something! But on the other hand, when we get together with our friends for a birthday or a celebration, it won't be just for the afternoon - it'll be for the whole weekend.'

Mount Hart Wilderness Lodge, 1,134 miles
The Gibb River Road takes us through more of West Kimberley's stunning gorge country before we turn off towards Mount Hart and through a landscape of puddingshaped hills covered with blue-green spiniflex - soft-looking, yet vicious to touch. Small, wiry and sporting an impressive outback beard, Mount Hart Wilderness Lodge's owner Taffy Abbotts moved up here in 1990; his wife Kim came later, as a backpacker, and stayed. It's quite a theme of our journey - the people along the road who came for a visit and never left, bewitched by the land's particular spell.

'I've built everything myself,' says Taffy, gesticulating. 'Houses, machines and computers. The road is closed during the wet and we're pretty much cut off for four months, but we work through it. I was welding a stand for the water tank in 45°C heat, and couldn't tell if the metal was hot from the welder or the air temperature.' As he talks, a number of galah birds squabble in the frangipani bushes around the cabins and flash their rose-pink underwings. 'I love the wet,' says Kim. 'I look forward to it - that solitude, that peace and quiet.' She smiles, stroking one of her tame dingos. 'Just... sanity.'

Broome, 1,417 miles
It's a long and beautiful drive to sleepy Derby - the town Pat Lacey used to visit for provisions twice a year. It's little more than a pit-stop: a shop or two, and a garage where barefoot Aboriginal kids sit eating ice cream on the forecourt. After Derby we hit tarmac for the first time in days and speed across a flat, featureless plain, dotted with termite mounds. The earth turns an almost purplish crimson and, suddenly, we find ourselves in town - attractive, laid-back Broome with its long, low streets of houses with verandas, flags flapping jauntily in the sea breeze, leisurely strollers and bicycling families. Rugged Kimberley suddenly seems very far away indeed.

We pass the last of Broome's pearl luggers - small, sailed boats that are a remnant of the pearling industry on which the town built its wealth - and head straight to the sea, the great white expanse of Cable Beach. Kids play football and catch crabs as the sun drops like a copper coin into the Indian Ocean. Back at the hotel, a few minutes in the shower washes off layers of orangered dirt. But it will take much longer for me to stop dreaming of that wild, red road rolling out before us in the outback.


The article 'The Top End' was published in partnership with Lonely Planet Magazine.