While lascivious mortals worshipped their brains out at the temple, the goddess, having just split up with Ares, god of war, was frolicking with new love interest Adonis. Spyros Constantiou, who sells oranges to sightseers, knew it would end badly. “She’d just broken up with the god of war, not the bloody god of hairdressers, innit?” he sighed. “Of course there was going to be trouble.”

He was right. Ares was persuaded that his separation from Aphrodite was only temporary and the Adonis kid was getting in the way. By law, gods couldn’t kill mortals... but there was a self-defence loophole. Ares realised that if he just so happened to be, say, a wild boar, in, say, the Akamas wilderness, and some pretty boy fancied his chances, then he could defend himself.

Adonis heard about the Akamas boar and planned to bag it. Ovid recorded what happened next: “As the boar broke away, Adonis speared it. The savage beast dislodged the bloody point and charged Adonis as he ran in fear for safety, and sank its tusks deep in his groin and stretched him dying on the yellow sand.”

He was dead by the time Aphrodite found him. As she carried his body from the woods, red anemones sprang up where drops of his blood fell. But I found no scarlet flowers. I’d expected her spirit to be here, wandering the groves in grief, but the goddess hadn’t stuck around. I decided to widen the search.

I travelled from Akamas to the capital, Lefkosia, where I saw crosses worn in her honour 3,500 years before Christ’s birth. I visited her sanctuary in the lost city of Amathus and then the ruins of the kingdom of Kition, where an archeologist showed me a gold coin from which she stared like a photo of a missing person who didn’t want to be found.

Finally, tired and thirsty, I returned to the Seven St Georges, and found the proprietor up to his elbows in wild honey. “Taste this,” he said, handing me a stick coated in gritty nectar. “It’s an aphrodisiac. You find the goddess yet?”

I shook my head. “Go back to Kouklia and look in the church,” he suggested.

The tiny Byzantine chapel at the edge of Aphrodite’s temple site was built with stones looted from the ruins. Childless and lovelorn women come from all over Cyprus to pray here, taxi driver Yiannis Theodolou explained.

“To pray to whom?” I asked.

“The Virgin Mary, of course,” he replied. “We’re Christians here.” Then he glanced over his shoulder, as though checking we were still alone. “But we all know who it really is. Even the Magi knew. When they brought myrrh to the stable it was a gift for the mother, not the child. A reminder of Adonis.” He shook his head.

“She changed her name and cleaned up her act, but she couldn’t fool us.”

Getting there: Cyprus Airways (020 8359 1333, www.cyprusairways.com) flies to Paphos from Heathrow, Stansted, Birmingham and Manchester; fares start from about £160. Charter airlines with seat-only deals include Excel (0870 320 7777, www.xl.com) and Thomsonfly (0870 190 0737, www.thomsonfly.com): from £121.

Where to stay: the stylish Elysium Hotel (00 357 2684 4444, www.elysium.com.cy), outside Paphos, has doubles from £142. For a great selection of rustic hotels, contact Cyprus Agrotourism (00 357 2234 0071, www.agrotourism.com.cy).

Getting around: Value Car Rentals (0800 040 7557, www.valuecarrentals.com) has a week’s inclusive hire from £118. Or try Holiday Autos (0870 400 4461, www.holidayautos.com).

Further information: the trail maps are available from the Cyprus Tourism Organisation (020 7569 8800, www.visitcyprus.org.cy).

Times recommends

• Overlanding then and now
• Live Q&A: ski fitness and injury
• Get the right payment card and deny Ryanair its hefty fee