Forget all the clichés about Australia’s cuisine being centered around tossing a couple of shrimps on the barbie, and its wines best for laying down and avoiding. These days, Australia is a land of organic cultivation, elegantly balanced wines and award-winning international haute cuisine. Thus, in the 21st century, a tour of Australia’s food and wine regions – the Mornington Peninsula, the Barossa Valley, the Adelaide Hills and Margaret River, to name a few – is a journey through a country that has long emerged from beneath the petticoats of Empire and is expressing itself as a stand-out, global gastronomic centre.

As the celebrated Sydney chef Mark Best told me as we sat in the cool confines of his award-winning restaurant, Marque: “Finally, Australia is sure of itself and of its place in the world. It’s a combination of no longer measuring ourselves against the Old World and also recognising that, geographically, Australia is part of Asia.”

For a month I travelled through the country from New South Wales to Victoria and South Australia and finally across to Western Australia, a 4,200-mile odyssey that took in all manner of vineyards, farmers’ markets, country restaurants, “three hat” haute-cuisine establishments, gourmet food vans, urban gastropubs and rural organic pubs. In the end I realised that, as vast as Australia is geographically, so it is gastronomically and viticulturally.

New South Wales

I began this Antipodean blow-out by meeting Mark Best and having dinner at his much-praised Surry Hills restaurant Marque, Gourmet Traveller’s Restaurant of the Year in 2012. Best has been named Australia’s Chef of the Year many times, and for the past two years Marque has been listed among the world’s top 100 restaurants. Unlike so many places in the El Bulli mould, Marque serves real food rather than presenting a culinary pantomime. So, although you get an 11-course degustation menu, it is very much in the tradition of new French cuisine.

“I worked at L’Arpège under Alain Passard, my inspiration is the French nouvelle school and my heroes are people like Passard, Pierre Gagnaire and Frédy Girardet,” Best explained – and his food reflects those influences. It was worth crossing half the planet just to taste his smoked eel with parmesan gnocchi and pumpkin, followed by the striped trumpeter with green tomato, verjus, potato paper, fish milk and roe. The degustation menu costs A$160/£90.

Sydney, not surprisingly, is replete with fine-dining establishments including Neil Perry’s Rockpool Bar&Grill and Peter Gilmore’s Quay, this year named among The World’s 50 Best Restaurants. However, Mark Best recommends Golden Century in Sussex Street, a 600-seat Cantonese restaurant popular with Sydney’s top chefs and costing only A$25-A$30 a head.

A rural alternative to bustling Sydney is Mudgee, a small town a few hours’ drive, or a 45-minute hop by plane, across the Blue Mountains. In the Wiradjuri Aboriginal dialect, Mudgee means “nest in the hills”, appropriate because the town is in the fertile Cudgegong Valley. In the 19th century, it was sustained by the region’s gold-mining boom and more latterly by coal mining. In recent years, the growth of low-key rural tourism has given it a new lease of life.

Soporific and gently amiable, Mudgee is much like the Hunter Valley was 25 years ago. Locals talk about its “humble brilliance” as a wine-producing region in the throes of a serious renaissance. There are 23 cellar doors within four miles of the town centre, and some excellent restaurants. I’d particularly recommend the Butcher Shop Cafe at 49 Church Street for a huge, unhealthy full Australian breakfast and a close-up of the locals gossiping, and Sajo’s, formerly the town’s pharmacy, for modern healthy Aussie cuisine in a stylish setting.

The Mudgee wine revolution is being led by Black Tongue, a group of young winemakers who have thrown off the area’s reputation for jammy, old-fashioned reds and are making modern, balanced wines which, if my tastings are anything to go by, are about to start winning awards. Already Jacob Stein, the 28-year-old winemaker at the family-owned Robert Stein.

Winery&Vineyard has been named Young Australian Winemaker of the Year 2012, and fellow Black Tongue members including Liam Heslop at Lowe, Josh Clementson at Skimstone Wines and Peter Logan at Logan Estate are surely on the verge of similar accolades.

Victoria

Melbourne’s long tradition of European cuisine was broken only relatively recently by the opening of Shannon Bennett’s Vue de Monde, offering a wild Australian degustation menu. Relocated from Normanby Chambers to the 55th floor of the Rialto building in 2011, it provides panoramic views of the city and surrounding ocean. Gastronomic flourishes include scrambled emu eggs and truffles, wallaby steak, and poached Pemberton marron (langoustine) with tarragon-spiked emulsion and salt dust. On departure you are handed a goodie bag of brioche and tea for the next day’s breakfast. Bennett’s head chef, Cory Campbell, says the menu is representative of contemporary Australian cuisine, with marron and wagyu beef as “core courses”. Expect to pay A$250 a head without wine and around A$400 if you include something from the extensive cellar.

If you’re after more traditional Melbourne-Italian fare, try Grossi Florentino at 80 Bourke Street or the marvellous Ombra, next door, run by Guy Grossi’s son, Carlo, and modelled on a northern Italian salumi (cured meat) bar. Food is served on rustic wooden boards and the home-made mortadella and the various salamis are outstanding. The wine list, featuring a good selection from Italy, also offers some excellent examples from Victoria.

But it is out on the Mornington Peninsula that the great viticultural treats lie. There, a band of clever eccentrics have shelved their main careers, thrown themselves into single-vineyard, small-production winemaking and turned out some of Australia’s most delicious pinot noirs and chardonnays. One of these Peninsula pioneers is Richard McIntyre, a surgeon-turned-winemaker who prefers to discuss the joys of whole-bunch fermentation to the internal organs of human beings. With the help of his daughter Kate, a Master of Wine, he makes not only the Moorooduc range but also the highly regarded Ten Minutes by Tractor wines with grapes from a neighbouring estate. As we taste the 2011 Moorooduc Robinson Vineyard pinot, Dr McIntyre declares it the best wine he has made at the estate.

Not far down the road is another career convert, Nat White, a civil engineer who first tasted pinot and chardonnay in Burgundy in the 1960s and liked them so much he thought he’d try to make some. He bought Main Ridge Estate in the 1970s, took a wine science course by correspondence and now makes about 1,000 cases a year. Their rarity, and the quiet charm of Nat White himself, are reason enough to visit the place, but the clincher is that it serves wonderful Sunday lunches accompanied by some of the estate’s rarer, older wines.

South Australia

The state’s principal food and wine areas outside Adelaide are the Barossa Valley (an hour’s drive away) and the Adelaide Hills (half an hour’s drive). Both are awash with big Australian characters. Maggie Beer, the former host of the long-running television series The Cook and the Chef, is one of them, whirling like a dervish among the diners, drinkers and shoppers at her eponymous Farm Shop in the Barossa. A pioneer of fresh, authentic regional produce, she opened the shop in the late 1990s and now serves picnic fare all day from 10.30am, so you can sit at the wooden tables on the deck, drink some local wine and contemplate the rural idyll.

As I looked out on 50 acres of olive groves, vineyards and orchards, Maggie pulled out a copy of Barossa Living, the local glossy lifestyle magazine. The cover featured a moody monochrome portrait of Peter Lehmann, the “Baron of Barossa”, who had died the previous week. “What a great loss,” she said. “Without Peter, none of us would be here.” The original larger-than-life, swearing, drinking, chain-smoking Barossan, Lehmann not only saved the grape-growing industry but also transformed this region from a mass-producer of table wine into one of the New World’s most successful wine regions.

The Barossa’s wine trails are sophisticated, varied and well organised, with cellar-door tasting rooms and excellent farm restaurants. At Charles Melton Estate, I had lunch on the small terrace overlooking the vines (the gourmet lamb pie with shiraz sauce is outstanding) and stayed overnight at the estate’s 19th-century Lutheran church, transformed into a rather charming two-bedroom guesthouse.

On the outskirts of nearby Tanunda, the Artisans of Barossa – a collective similar to Mudgee’s Black Tongue group – have also set up a cellar door and restaurant with a view of the Barossa vineyards. The chef-in-residence is Mark McNamara, formerly of the Louise, a smart country retreat in the Barossa, which means the food is excellent. His Sunday long-table lunch – five courses and a selection of the Artisans’ wines for A$95 per person – comes highly recommended.

But wine is the real draw of the Barossa, a region on the way up. Several of its small-production, multi-varietal wineries have achieved five-star status in the 2013 edition of James Halliday Australian Wine Companion. Among them are Peter Schell’s Spinifex label, Jaysen Collins’s 
Massena, and Sons of Eden, whose principal winemaker, Corey Ryan, has worked at Henschke and Penfolds and is a veteran of 20 vintages.

My next stop in the Barossa was Glaetzer, run by Ben Glaetzer, whom I had last visited six years ago. Back then, he had just been declared Australia’s Young Winemaker of the Year, so I was curious to know what he made of the current generation of young bucks, Black Tongue and the Artisans of Barossa. “I’m only 35 myself,” he said, “and some of these ‘young tyros’ are the same age as me and quite a few are older.” That settled, we proceeded to taste Ben’s signature wines – Amon-Ra shiraz and Anaperenna cabernet-shiraz blends – and his impressive entry-level Heartland wines. These are the big, bold Barossa reds of yore, but perfectly balanced and with a less heavy-handed use of oak. There is no attempt to recreate the wines of France in the southern hemisphere, an indication of Australia’s impressive self-confidence.

On my final day in South Australia, I had lunch in the Adelaide Hills with John Edwards, creator of The Lane Vineyard and its excellent bistro. A bear of a man, he said he was making “European-style wines with sunshine in them” – and although he claimed not to be interested in wine competitions, he was clearly delighted that his 2012 Block 14 shiraz had just won The Lane its first major prize. The restaurant and tasting bar look down on the vineyards and the food is as fresh, local and delicious as I had come to expect of Australia’s winelands. After an Antipodean feast of cured ocean trout, nashi pear (what we call Asian pear) and sea parsley, followed by masterstock braised pork belly, I left South Australia with a heavy heart and a burgeoning waistline.

Western Australia

The final leg of my month-long odyssey took me to Margaret River, three-and-a-half hours south of Perth, which produces more than 15 per cent of the country’s fine wines. Over the past decade, it has grown as a tourist destination, thanks mainly to the refurbishment of the Perth-Bunbury Highway, which has shortened the drive by 40 minutes and made the journey so much easier.

Bordered by the Indian Ocean to the west and ancient forests to the east, Margaret River is a laid-back gourmet enclave with more than 60 cellar doors. Several wineries have restaurants serving lunch, while fine-dining options include Cape Lodge, where chef Tony Howell offers an impressive tasting menu (Esperance scallops, Exmouth prawns, Gracetown dhufish, quail) with wine pairings for A$220, dinner, bed and breakfast.

The first vine planting in Margaret River was in the 1960s, when three doctors – Tom Cullity of Vasse Felix, Bill Pannell of Moss Wood and Kevin Cullen of Cullen Wines – decided to test the theory that the region could produce high-quality wines. As they subsequently proved, the climate and soil are ideal for growing cabernet sauvignon and chardonnay. In fact, compared with Bordeaux, Margaret River has 25 per cent fewer days when temperatures rise above 30C but enjoys more sunshine hours during the growing season – viticulture perfection.

My first stop is the Cullen Estate where Vanya Cullen, the daughter of one of the founding doctors, is making some of the best wines in the region. She was the first woman to be named Australian Winemaker of the Year in 2000 and was “Green Personality of the Year” in 2011 for her work in sustainability. Cullen is a certified biodynamic estate which Vanya describes as “a winery with a biodynamic garden”. This rather understates the case, for the food and wines served in the restaurant are memorably good and the jam, the pickle and the honey are exquisite. I have never been a great consumer of honey, but this was so good it was addictive. And the barramundi I had at lunch at Cullen’s was the freshest and sweetest I have tasted.

Fifteen minutes south is another of the founding wineries, Leeuwin Estate, but this one was created not by a doctor but by a surfer. In the late 1960s, Denis Horgan came across the 120-acre property while surfing the famous Margaret River waves and was quietly raising his young family on his new farm when the California winemaker Robert Mondavi offered to buy it. Horgan thus became aware of its viticultural possibilities and, with input from Mondavi, one of the region’s great estates was born. Today, it produces classic cabernets and chardonnays, the latter described by Wine Spectator as the greatest white wine Australia has produced.

Today, Leeuwin is much more than a wine estate and has become something of a cultural gathering place. Since 1985 it has staged summer concerts in which the performers have ranged from major European philharmonic orchestras to Dame Kiri Te Kanawa, Shirley Bassey, Roxy Music and Sting. It also now boasts a substantial art gallery, born out of the Art Series labels on its premium wines and now comprising more than 100 works created by significant Australian artists.

Leeuwin’s large, award-winning restaurant really is a treat, overlooking the rolling lawns and karri trees and serving up excellent contemporary Australian cuisine (try the freshwater Blue Ridge marron in a bisque with crème fraiche). I’d particularly recommend the “Wine and Food Flights” tastings, where a selection of the estate’s premium wines are matched with various dishes.

By now I was ready to leave Australia. After one month on the road, 4,200 miles travelled, 30 wine estates visited and 40 restaurant and vineyard tables sampled, a serious fast lay ahead. However, there was one temptation remaining. As I was about to leave Margaret River, I was persuaded that there was one more food hero I had to meet – a young chocolate-maker by the name of Josh Bahen. For a decade, he had been a winemaker at Moss Wood but, on a trip to France, bit into a piece of chocolate “that tasted like fresh fruit” and decided, with his wife Jacq, to set up a small chocolate factory on the family farm. Bahen&Co was born.

Just as the wines I had been drinking and the fresh, well-prepared food I had been eating represented the new, confident, independent Australia, so on this small Margaret River farm I discovered a dessert to beat all desserts. Nothing I have tried from Marc Demarquette, La Maison du Chocolat, Rococo or even Pierre Hermé matches Josh Bahen’s post-prandial delights. Vive the new Australia. Now for the gym.

What to drink from Australia's top cellars

Region: Adelaide Hills. Textbook Austrian varietal grown under Australian sunshine.

Reds