The article first appears in Vol. 29: Taste.

Walking Walking home late one night through the shadowy streets of Mdina, Malta's "Silent City", we notice a triangle of light pouring from a doorway. Just inside, a tray of golden pastries ecked with giant sugar crystals blocks the threshold, balancing on a battered metal stool. Behind them, two men in flour-dusted vests and gold chains shovel a giant, duvet-like mound of dough into a wooden container, while a row of dented baking trays hum in the oven. We had taken a convoluted route home, abandoning the maps on our phones in favour of weaving our way blindly through the city's maze of cobblestone streets.

Living up to its name, Mdina at night presents itself like a secret - a locked chest of latched windows, empty alleyways and tightly closed doors. In the midst of all the silence, this little bakery appears like a glowing invitation on the street corner. We squeeze past the trays and go inside, where the two bakers blink at us before confidently explaining: ''We have the city's best bread. Come back in the morning when it's fresh." We ask them if they will be baking all night. "Yes, of course," one of them replies, finishing off his last drops of coffee. "We are here every night. The city needs bread."

In truth, we had come to Malta with very little idea of what the country had to offer in the way of food. Like most people, we were more familiar with images of its deep jewel waters, windswept stone formations, art-filled churches and ancient cities than its cuisine. After a week of exploring the Maltese archipelago in a jittery old car, it became clear that the true way to taste the region is to give up trying to find the newest, shiniest restaurants (there aren't many) and instead engage with the everyday eating rituals of its inhabitants. This is a place where friends gather under blinking strip lights in faded bakeries, eat freshly caught shrimp at dated restaurants in church squares and make use of local markets brimming with produce ripened by the island's 300 days of sun a year.

Much like its rugged landscape, Malta's food scene is something that takes time to understand. Unlike neighbouring Sicily, where food is at the centre of everything, here in Malta it is enjoyed in simpler ways: hidden behind doorways, burrowed in underground vaults or deep inside family homes. The best moments of our trip were spent with locals passionate about perfecting their craft and shedding light on the real, honest food of the islands, including natural winemakers, shermen and bakers sending us home with the promise of fresh bread in the morning. Food is wound quietly into the fabric of everyday life here, rarely shouted about or overworked - which makes these rare moments even more delicious.

We never did find out the name of that bakery...

Day 1

Valletta is Malta's miniature capital, built atop the thirsty rocks of the Sciberras Peninsula with the golden stones of its Grand Harbour plunging into the Mediterranean. We wake up at Casa Ellul, a Victorian-era palazzo-turned-boutique hotel filled with restored tiles, concrete walls and velvet nishes. The soaring dome of Our Lady of Mount Carmel Basilica heaves over our little terrace, filling our room with the sound of bells and forcing us out of bed and into the sun.

After a head-spinning cold brew at Lot Sixty One Coffee Roasters just down the road, we spend the morning losing our way in Valletta's web of streets, which are lined with wood-panelled apothecaries and tiny shops selling handmade lace and candy-coloured plastic statues of the Virgin Mary. So much of the city feels untouched by contemporary trends, happily snoozing away in the sun while the shopfronts fade - and look all the more beautiful for it. Exploring the city navigation-free, we soon discover how easy it is to end up at the water's edge, pulled along by the narrow streets until they simply run out.

Following a mid-morning scoop of Sicilian pistachio ice cream from Arena, a Verona-born ice-cream stall (whose vendor urged us to "tell your friends!"), we scoop almonds from a wooden drawer at George Zammit, an emerald-fronted spice shop filled with sacks of beans, spices and dried herbs with the heady scent of anise rising off of every surface. Classic confectionary shops, such as the gold-dipped Caffe Cordina, sell almond tarts, crumbly cannoli and cakes dressed in hot-pink and peppermint- green icing. "This is the land of honey," a waiter proudly tells us, as we tuck into a Maltese honey ring. Elegant old women prop themselves at the marble-topped tables beside us, sipping espresso and patting cake crumbs of their lips with linen napkins.

We push the car to its limits that afternoon, tackling the potholes on the path to St Peter's Pool. Here, swimmers stretch out on a near-perfect semicircle of smooth sandstone, diving off its sharp edge into the clear-blue water.

Afterwards, we wander the waterfront of Marsaxlokk, a traditional shing village known for its daily open-air market. Primary-coloured shing boats no bigger than a park bench bob in the Roman-era harbour, while no-frills seafood restaurants serve freshly caught fish best enjoyed with a cold pint of Cisk lager, as one sherman tells us.

Day 2

Just 20 minutes from Malta by boat, the island of Gozo feels much further away from its bigger sister - and, in many ways, from anywhere else on Earth. The sun-cracked land, ancient citadel and whisper-quiet villages are watched over by a statue of Christ, who stands open-armed at the top of Tas-Salvatur Hill.

We drive straight to Thirtyseven, a boutique hotel hidden down a dusty side road in the village of Munxar. This 400-year-old farmhouse is run by Patti and Giuseppe, two ex-fashion industry professionals who fell in love with Gozo's "mystical beauty" on their first visit. All 37 rooms are designed by Patti, who also sells wares from her travels in a vaulted on-site shop. Light, healthy meals are made using fresh catches and local produce in the tangerine-coloured kitchen, and at breakfast the glassy dining room fills with the smell of freshly baked apple cake, ginger cookies, coffee and still-hot madeleines. After encouraging us to "be lazy for a while", Patti leaves us by the pool in the garden, where butter flies dart between palm and pomegranate trees.

This little hideaway, with its contemporary art and plush colour palette, seems to hint at Gozo's quiet glamour. "Artists, sculptors and musicians are drawn here. A lot of people are mesmerised by it," Patti tells us. "People have gardens, the sea, all this beautiful light. We forget what nature can teach us, and what we can get back from it. Gozo is the perfect place for people to come and reconnect. And sometimes they just never leave."

At lunchtime she points us in the direction of Mġarr ix-Xini, a glittering bay at the end of another treacherous path. People gather on crooked tables at its simple restaurant to eat the island's freshest mackerel, red snapper and sword fish, grilled at the water's edge by the sherman who owns it.

Back at the hotel, Patti piles us into her turquoise Jeep and drives us to the northern edge of the island. We climb the rocks around Dwejra Bay before driving past Qbajjar Bay to the Xwejni Salt Pans. Sparkling salt emerges from pools of seawater on a chequerboard of stone-cut Roman pans.

"It looks like the moon. I don't think there's anywhere on Earth that has water this colour," she says, looking past the pans towards the sea as the sky turns lilac. A few swimmers bob in the water, while their dogs trot along the rocks beside them. "This island is magical when you give it time. It can heal you."

Day 3

After scaling the vertical footpath that leads to it, the cool, clear water of Wied il-Għasri is something of a reward on a hot day. This narrow bay is hugged by craggy rocks and underwater caves, with tangles of caper bushes (and the odd adventurous climber) clinging to its edges. We leave our things in a pile on the pebbles and swim up the deep corridor of water until it opens up into the sea, returning a while later to find ourselves completely alone.

With salty hair and a sun-induced thirst, we make a pit stop at the Lord Chambray taprooms. This local craft brewery makes beer "to be a companion to everyday life in Malta", naming each brew after one of Gozo's natural beauty spots. With the distinct feeling that we could happily stay on the island for the rest of the year, we finally wrench ourselves away and return to the hotel to pack up to leave.

On the way to the ferry with Patti we stop off at Gleneagles Bar, where local shermen drink amber ale under a ceiling of antique diving nets and fish sculptures. "You should see how wild it gets in here sometimes!" she laughs, patting owner Tony on the arm.

Day 4

"Where is everyone?" we ask each other, walking back to the car past the locked-up shopfronts and empty squares of Cospicua's centre. Back in Malta, we'd spent the day exploring the "Three Cities", a triangle of sleepy harbourside neighbourhoods peppered with limestone buildings and peach-domed churches. Our last stop is Senglea, where we eat delicate plates of fish and yogurt-topped vegetables at Hammett's Maċina, a restaurant on the waterfront adorned in brass and marble.

In Valletta that night we sip dangerously strong paloma cocktails on the steps outside hairdresser-turned-bar Cafe Society before heading to the stone vaults of Noni. This restored bakery serves Maltese classics with a gourmet twist, silencing us with bowls of fennel-flecked pappardelle, grilled octopus and roasted rabbit.

Day 5

We end our journey in Mdina's car-free centre, a 4,000-year-old city entered through a grand baroque gate where marble angels float above lemon-yellow doorways on streets lit by gas lamps. It's easy to get lost in this strange, quiet place - and we do, working up an appetite as we stumble through its chipped alleyways and cobbled side streets.

We end up in the queue at Crystal Palace, a bar where locals crowd around sticky plastic tables beneath blinking television screens. According to many, this is the place for the island's best pastizzi, the ubiquitous Maltese pastry traditionally stuffed with ricotta or peas. We pay 60 cents for two, which are slid into paper bags straight from the oven's blackened baking trays.

Earlier that day we'd driven uphill from the little town of Siġġiewi to Mar Casar winery, where owner Mark Cassar ushers us inside holding a pipe, his hair a storm cloud of grey. Using the ancient methods of Georgian winemakers, he produces a small range of natural wines using earthenware "kvevri" (vessels) buried beneath sand in his cellar. Eighteen years ago, while suffering from severe depression, Mark began taking walks along the sea. Invigorated by the landscape, he bought three hectares of farmland overlooking the water and began experimenting with natural winemaking. "Just like that, I stopped taking my medication - and here we are," he tells us, sloshing amber- coloured wine into our glasses. "Natural wine has an energy, a certain magic - it's alive. This is a kind of alchemy."

After a few too many glasses ("it leaves your system in 20 minutes", Mark insists), he walks us up the hill to his vineyard, where long twists of grapevines grow beside wild herbs and prickly pears. We stay there for a while listening to his stories, watching him scoop up the earth in his hands and pick olives from the trees with the whole of Malta spread out below us. He pushes a bunch of yellow wild-fennel flowers into our hands. Their sweet, aromatic scent lingers on our clothes for days.