“ONE man’s gaol is another man’s heaven,” says Ron, a businessman from Perth, the second most sun-soaked city on earth, he tells me, “after Honolulu”.

“Look at us now,” Ron explains, elucidating his thesis. “We’re plonked on a flamin’ Emirates jumbo. Can we escape? Would you even want to?!” He and I have been happily arguing over Australia’s convict past. I gently remind him that in ‘the good old days’ Aussie gaols were far from heaven. “Here come the cabin crew,” he gestures, “carrying tucker.” Ron raises his glass.

When the plane touches down on Western Australia’s paradise coast near the suburbs of Perth, we say our goodbyes. “Free at last!” he says with a barbed sarcastic smile. “Where are you off to?” “Fremantle gaol,” I reply. He looks doubtful. I’ve lied. But not quite.

Half an hour later, 20 miles south, I check into the Esplanade Hotel, a Fremantle icon. I stand on my balcony staring at views of the harbour beside which seafood restaurants congregate all down the boardwalk frying snapper, calamari, barramundi.

The boardwalk tonight is politely crowded. There, the strolling classes of Freo (no one bothers with the full moniker), come after work to sink a few tinnies of ice cold grog and watch the horizon swallow the sunset.

My conscience pricks me. Did I fib? (Ron might be reading this, after all). Well, actually no. The Esplanade slummed it as Freo’s first prison back in the early 1850s, when, as a warehouse, it was temporarily used as the convicts’ doss house. During the day they left to hew rock and build the prison, each night returning. One day they checked out, and didn’t come back, moving instead to their rocky new-build perched on a hillock, and there they faced years of taunting, grief and incarceration.

I plan to taste the Doing Time Tour the following morning, but first I head to Cicerello’s on Fisherman’s Wharf, to savour the famous fish and chips. Beside the takeaway bar, a notice above a fish tank containing exotic-looking finned species, spells out the message: "These fish are poisonous. Do not put your hand in the fish tank!" In case you possibly can’t read English, or don’t get the message, they’ve helpfully painted a skull and crossbones near the warning as a deterrent.

Since other body parts haven’t been specified I contemplate climbing up and risking a toe. But the burly fryer guy looks meaner than the allegedly poisonous fish. I collect my food and head to the safety of the marina where gulls have gathered en masse for their nightly Alfred Hitchcock re-enaction of scenes from The Birds.

The fish and chips are crisp and delicious. Then comes sunset. The gulls flap their wings, preparing to swoop. I eat with food tucked into my jacket, wipe my mouth clean, then head to bed. Alas, I don’t sleep.

I am up with the street-cleaning carts, the joggers, greeting sunrise. Even at this hour Freo’s breakfast cafes are clinking into aromatic action. I grab a coffee, a king-sized muffin, and read in the paper that yesterday’s temperatures were so sizzling someone messing about in the 'burbs had been baking cupcakes on the bonnet of their limo!

Looking around me, the city centre with its dog-legged, narrow highways, and small pedestrianised piazzas, oozes brick-and-stone built charm. It is low rise and human in its scale, retaining a retro look that derives from a lack of prosperity at a time in the 20th century when most other Australian cities were demolishing and rebuilding, aiming skyward with glass and chrome. Most of the old Victorian legacy remains in Freo’s shops, cafes, galleries, strip after strip of colonial architecture, awnings draped over footpaths, occasional statues among the palms in leafy squares.

Hugging the shade, I make my way to Old Fremantle Prison, a limestone citadel shining brightly on a mound above the streets that run to the harbour and the sea. The street names – Essex, Norfolk, Suffolk Arundel, Howard – superimpose Freo’s English heritage on its millennia of Aboriginal nationhood, when the place was known as Manjaree, long before Captain Charles Fremantle hove into view along the horizon in HMS Challenger in 1829.

It was 20 years later, with the coming of the convicts, that the town gained stone built permanence. I am staring at what they built: a narrow gateway between two imposing octagonal towers, today too narrow to let a fire engine in. It’s the entrance to the prison. "Not flamin’ likely to go up in smoke mate," says a punter in the crowd near the Convict Cafe as we wait for the tour guide to call us.

Tall, broad shouldered, with fierce black eyes and a beard to match as thick as a fleece, our guide instructs us to call him Boss, just like the convicts did the guards. Got that? “Yes boss,” we chant in unison. For we are scum, sent here to do time and build the prison. He cracks the whip to the manner born. And the tone is set for an entertaining 80 minutes during which Justin shows us the inexplicable imprint of a ghost face in the window of the chapel. “She was imprisoned for the murder of her three kids,” he says. “It’s a mystery how it got there.”

He shows us the cells, then the infamous ‘whipping post’ and the gallows, and tells us tales of Freo’s most reprehensible inmates, the ‘untouchables’. We hear the story of Australia’s most daring prison break in 1876, when a band of Irish political prisoners, the Fenians, bolted to safety, reaching an offshore American schooner, the Catalpa, and sailed to freedom. “This was a tricky place to bust out of and not get caught,” says Justin, mentioning over 40 executions and over 200 attempts to escape. But you’re free to scarper,” he tells us at last. When someone says “Yes boss.” He finally smiles.

I head to Bannister Street downtown, and the Hougoumont Hotel, named after a prison ship. There, in reception a wall has been faced with a roll of ‘honour’ listing convicts landed from England, among them the Fenians who beat the odds.

This touching footnote to Fremantle’s past attests to the city’s history-consciousness. Ryan Mossny, a bear sized Aussie who runs Two Feet and a Heartbeat walking tours, has Freo’s past at his fingertips as he threads his way on a two-hour informal stroll along some of the best-preserved stylish street fronts in Australia, taking us back to Aboriginal occupation and on to the making of modern Fremantle, showing old and new adapting – as in the Roundhouse, a doughty stone fortress, the oldest building in Western Australia, once the scene of notorious hangings, now home to the hanging of pictures and tapestries in its galleries, showing the work of a local co-operative.

“We get more visits from flies than people,” someone says, as I gaze past the pictures of blazing skies to families sunbathing outside in the afternoon breeze. The breeze has been nicknamed the Fremantle Doctor because of the balm it brings to scorched flesh. The scene entices me to step out and buy and ice-cream.

The Old Gaol and Roundhouse are on the trail of Fremantle Tram Tours, with a ghost tour after sunset on Friday nights to invoke the spectres of convicts and malcontents. But music and a bite are more my thing, so, after an al fresco drink at Little Creatures Brewery, outside a massive converted boat shed on Fishing Boat Harbour, I change in my room and head for The Mantle which spills on to Beach Street, and there, to a shoulder-shimmying back-beat I take in great wall art and a choice of international cuisines, surrounded by Freo’s bling and megabucks young middle-agers, loose limbed and with dentistry to die for.

A guy two tables away waves and smiles at me. Do I know him? Inside his mouth it is Eldorado. I tackle my taster plate of cuisines, then head through the buzz to Bathers Beach House, beyond which the moon across the calm ocean shines down on the spot were just three hours before the sun had been wowing diners with the speed of its descent.

Taking sips of Margerita, I hear Freo’s Friday night kerfuffle, the chatter of happiness, or alcohol, or sentiment, while the necklace of lights on the esplanade marks the coastline, and through the darkness from above comes the sound of a jet plane. From there the splash of lights below must seem like a miracle surrounded by so much darkness—the vastness of ocean, the barely populated outback of Australia. Perth and Fremantle, are lonely cities, and it strikes me that their capacity for revelry is their rage against the vastness, against the dying of the light, combined with a knowledge that, being remote, they can do much anything they please.

“Been to Rotto?” someone asks me, meaning Rottnest, the paradise island just offshore. “Been to the Saturday morning market?” chimes someone else, underscoring what a friendly place this is, if you happen to answer.

The Saturday market is all it’s cracked up to be. Full of music, smells from the delis, the sizzle of bacon, a palmist trying to read my glance, frock stalls and jewellery stalls. I buy a pair of silver kangaroo earrings for my wife, and step into the street.

Out there, a busker plays Waltzing Matilda, a waft of nostalgia adrift in a city moving inexorably forward. “Take care, have fun,” shouts someone behind me. I tip my shades to nod assent, to embrace the heat.

TRAVEL NOTES

Getting there: Emirates Airlines (www.emirates.com) flies daily from Glasgow to Perth from £709 return.

Where to stay: The Esplanade Hotel (www.rydges.com/fremantle) had doubles from £128 per night.

What to do: Fremantle Prison Tours (www.fremantleprison.com.au) offers tours from £12 adult, £4 child.

Two Feet & a Heartbeat Walking Tours (www.twofeet.com.au) has 2 hour tours from £27 adult

Further information: Tourism Western Australia (www.westernaustralia.com)