Stiff from the previous day's exertion, we set off at a leisurely pace, anticipating an easy paddle downwind, over long and gentle swells, skirting around the zig-zagging north coast. In Marsalforn, the seaside resort of bland four-storey apartment blocks that cater for most of the tourists who visit Gozo, we stocked up on food and water. The town is backed by the Marsalforn Valley, a wide and undulating valley of terraced fields, fringed by buttes. Towns sprouted on the two largest hills, pinned by the large baroque churches that tower head and shoulders over the two-storey limestone houses - townscapes that are characteristically Gozitan, the extravagant churches testimony to the islanders' devout Catholicism.

It took us a lazy hour to reach the cove at Ghajn Barrani, which means "The Foreigners' Spring" after another legend. The half-submerged boulders were tricky to navigate around, and it would have been impossible to get to the small strip of sand if the sea had been even mildly rough. Beaching the kayak, we walked upslope towards Dragut's Rock, a pyramidical boulder embedded in the clay halfway up the slope, where we ate a whole loaf of bread with cheese and onions and tomatoes. The small bay with its turquoise water and half-submerged boulders was set before us like some outdoor abstract art installation, the warm-amber of the rocks contrasting nicely with the greenish-blue hue of the sea. We could just make out the trickle of the spring that was supposedly discovered by corsairs plying the central Mediterranean. They landed here often, stocking up on fresh water and looting the fields up-slope for vegetables. One day, the legend goes, the master pirate Dragut Rias spotted a vineyard and sent one of his slaves to fetch him some grapes. The slave was ambushed by a farmer, and in his flight he managed to tear a few branches of vine. Dragut was so angered by this sacrilege (the Prophet Mohammed, it is said, forbade the destruction of vines) that he tied the slave to this rock and burned him alive.

"Each corner revealed a new vista. The sandy beaches looked like splashes of orange paint..."

Dragut was indeed an ambitious corsair - in a devastating raid in 1551, this Ottoman General captained a flotilla that dragged the entire able Gozitan population, 5,000 out of 5,500, into slavery - but the story has obviously been embellished. These stories, high on Catholic propaganda, were fanned by zealous Catholic priests among a people much given to superstition and lore and fantasy.

Later, I was thinking about the Gozitans' penchant for fantasy when we stumbled on a fisherman in his luzzu, the baroque wooden boat of indigenous design. His name was Paul and he was eager to talk after a whole day spent at sea alone. Like most Gozitans, in his teens he had emigrated, spending four years in Australia and ten years in Canada doing menial jobs. He returned to Gozo for a holiday in 1974, and ended up staying, taking over his father's fishing outfit.

"Fishing is in my blood," he said, scratching his stubble and playing with the folds of skin on his lined face. "I remember my grandfather fishing."

Paul had been unspooling trammel nets, putting out a three-kilometer wall of nets in which fish - squid, barracuda, scorpion fish, angel fish, mackerel, bogue, red mullet, painted comber, little tunny, and so on - got caught by their gills at night. "I work every day. When it is stormy, I mend nets or build new ones, and I scrape just enough for my family. That is the life of a fisherman. Our problem is that there are too many fishermen these days. When I started, I used to catch three crates of fish from three pieces of nets. Now I need seventeen pieces of nets to fill three crates."

I studied the luzzu, painted with bands of green, orange, red and beige, a baroque design flowering on its side, and the Eyes of Osiris carved on its hull. These eyes were symbolic, supposedly leading fishermen to areas where fish are abundant.

"You want to buy it?" Paul's eyes were permanently squinted. "I'll sell it to you. I have another one. This one is as old as me: 60 years, and it was my father who bought it."

"I know someone who might be interested," I said.

He clucked his tongue. "There is a problem. Old age has turned my heart soft. A buyer turned up the other week and I couldn't bring myself to sell her. I am kind of attached to her. I'll sell it to you when I retire."

I asked him whether he did anything to protect himself from curses and bad luck.

"Of course. You don't take me for a fool, do you? I always keep an olive branch near the engine. And--" he tilted his face towards the sky - "I have faith in Him. The man who strives honestly is rewarded. Sometimes I don't catch fish for some days, and I keep my faith, and then God gives me a large catch to make it up for me."

I was finding the northern coast more interesting. It has more nooks and crannies, and the landscape is more varied and colorful. We were passing green slopes covered with grasses and tamarisks and prickly pears and beards of bamboo, the land folding into a series of bluffs and valleys crowned by amber inland cliffs. Each corner revealed a new vista. The sandy beaches looked like splashes of orange paint, and the parts of the coast outside bays were pearled by boulders that had cracked off the cliffs and tumbled to the water's edge. All day the swell nudged us along in a shallow and azure and clear sea.

At San Blas, where we landed for the night, we got a close look at the orange-red sand that is unique to the Maltese Islands. A small crescent sandy beach, San Blas is backed by a valley of citrus orchards, and at the base of the inland cliff that crested the slope we could make out the layer of sandy bedrock: the redness is nothing more than iron which is leached inertly in the alkaline Maltese soils. The sand is formed by un-reactive aggregates of iron.