When it comes to Sicily, memory supplies all kinds of invisible dramas, from Persephone being grabbed down into Hades near craggy Enna, to the Athenian fleet’s destruction in the battle in Syracuse harbour; the mafia’s rise, fall (under Mussolini) and rise again (under naive American sponsorship in 1944); and all the post-war dramas associated with the island’s endemic violence. You can’t see them, but all are memorable.

We first went to Sicily 50 years ago. The boat sailed from Naples in the late evening, allowing time for dinner at one of the dockside restaurants, each fronted by a string orchestra, in full fig, mounted on a stepped dais, with a carnationed conductor — and sometimes a tenor, bulging with Gigli’s repertoire.

The following morning, in Palermo, our horse-drawn cab clopped along wide, palm-lined avenues of crumbling baroque villas. All were later bulldozed to make way for tower blocks that are themselves crumbling, thanks — if that’s the word — to the mafia, which is big in the (substandard) concrete business.

This time, with only a week to spare, we landed at Falcone-Borsellino airport, renamed a few years ago in honour of two brave magistrates, Giovanni Falcone and Paolo Borsellino, the first to persuade gang members — known as pentiti, the repentant — to give evidence against the regime of the sadistic psychopath Toto Riina, who capped all capos, and topped more than a few.

Falcone and Borsellino were guarded night and day, and travelled in unmarked, armour-plated cars. However, nothing could protect Falcone and his escort from the huge charge of explosive that, in May 1992, mangled them as they returned from Rome. It blew up in a culvert on the way from the airport into the city.

The outrage was so shameless that, like the Omagh bombing, it seemed to change the social and political climate. When the prime minister and members of the government came to Palermo’s huge, honey-coloured cathedral for the funeral, they were manhandled by furious Sicilians, for whom basta was basta. Two months later, Paolo Borsellino too was murdered. Who did it? “Who is still alive?” is the mafia’s stock answer.

A loud Women’s Lib meeting was in progress when we walked down the long street past the duomo to the Cappella Palatina. One of the slogans on a nearby wall read “Il integrismo non è lontano — habbiamo il Vaticano”, which means “Fundamentalism is not far away — we have the Vatican”. Sicilian women, notoriously pious and put-upon, are beginning to have had enough of the old rules, and rulers.

A decade ago, when we were in Palermo, the Cappella Palatina was having a prolonged facial. It was built by Roger II, the Norman king of Sicily, between 1132 and 1140 — its newly cleaned mosaics made by Byzantine craftsmen, the stalactitic ceiling by Arabs. The Norman cathedral at Monreale, eight miles outside Palermo, is grander, with a majestic Panto- crator promising selective salvation from above the altar — but it lacks the closeted refinement of Roger’s private cappella. Roger built Monreale as one in the eye for the archbishop of Palermo, with whom he had quarrelled. It’s the most sublime example of take-that in art history.

Half a century ago, the roads were narrow, potholed and slow with the traffic of traditional carts, hand-carved and brightly painted. Shuttered villages stank sweetly of straw and donkey dung. The few carts to survive the Fiat revolution are now museum pieces. A late starter in Italy’s economic surge, face-lifted Sicily is putting on a new Euro-funded smile for the benefit of strangers with the cash (and the nerve) to back it as the next Tuscany or Puglia.

It has the beauty, the beaches, the variety and, God knows, the history. The island ’s past makes it a special and hard case, but investment in new hotels is booming. Could it be that the mafia’s Men of Respect are really turning respectable and hanging out Ben-venuti signs? Don’t ask; enjoy.

We went counterclockwise around the island, along the EU-funded autostrada, to the southwest, through traditional mafia country. Partinico, Castellammare del Golfo and Castelvetrano used to be unwelcoming and inaccessible. None is as sinister as Toto Riina’s Corleone (off the Agrigento road), but Partinico was the home, in the 1940s and early 1950s, of Salvatore Giuliano: the Sicilian Robin Hood, as sentiment liked to label him. In fact, he was more a robbing hood. After making worldwide headlines, he was betrayed by a trusted henchman. The carabinieri took the credit, but the mafia had had enough of Giuliano’s attention-seeking. Clever murderers don’t advertise.

We were heading for Mazara del Vallo, in the unfavoured flatlands east of Marsala. On the way, we deviated to Segesta, where I was only slightly happy to bump into my old college friend Professor Knowall.

Times recommends

• Oasis of the Seas: the Times review
• The 20 best new year party places to stay
• Green Spaces 2009: are you the winning writer?