After Rome, Africa,” the northern Italians say. The slogan encapsulates Italy’s enduring division into the rich north, with its proud Renaissance civilisation, and the poverty-ridden south, with its ragbag culture and allegedly dodgy inhabitants.

What they have been dodging, for many centuries, is the acquisitive domination of people marching in from the north.

Puglia — the region, facing east, which covers most of the spur on Italy’s heel — is less African than Greek: Patras, on the northwest corner of the Peloponnese, is only a few hours away. As early as the 8th century BC, the Spartans came across, whacked the native Messapians and helped themselves to choice chunks of southern Italy.

The whole region came to be called Magna Graecia, and mangled Greek can still be heard in remote hill villages and in their folk songs. The local genetic soup is rich with outlandish ingredients: after the Greeks and the Romans, German, French and Spanish princes brought their courtiers and their bullies to carve out fiefdoms and lord it, for a while, among the olive groves. The landscape bristles with the castles and churches of departed captains and deposed kings.

Puglia on a plate

Michelin stars count for little here, writes Fiona Sims. Instead fresh flavours and rustic cooking offer a genuine feast

• 50 of the world's best food blogs

• A family truffle hunt in Italy

• Milanese feast on a tram

Borgobianco Resort and Spa, Italy

Colour therapy and luxury on a perfect scale at an independently owned hotel in Southern Italy

• Il Pellicano spa, Porto Ercole, Italy

Related Links

• Puglia: the foodie guide

• Puglia on a plate

• Puglia: the complete guide

Landing at Bari, we planned a looping trip all the way down the spur on the heel to Gagliano del Capo, on the extreme southern tip. The charm of Puglia lies in its variety. Its unique monuments are the enigmatic trulli. Like limestone mushrooms, with conical shingled roofs, they pimple the stone-walled fields as far north as Barletta, but become a hefty rash around Alberobello, a pretty touristic centre where every other shop and house is a parody of the form.

Nobody is sure who made the first trulli, nor why. Originally too small to house anything but a gnome, they seem to stand for something alien and inexplicable.

Equally alien and inexplicable, but hugely more ostentatious, is the 13th-century Castel del Monte, built by the emperor Frederick II of Swabia, who grew up in southern Italy. His German peers mocked him as “the Puglian kid”, until he went north and imposed his majesty. The third of his diplomatically selected wives was Isabella, daughter of England’s King John.

As you drive across from the coast through Andria, his castle becomes visible, like a fat crown turreted on the bald head of the biggest hill ahead of you. Nothing could be more carbuncular or more conspicuously useless.

The building itself is an architectural exercise in the eight-times table. There are eight towers, each octagonal, each 80ft high, containing eight rooms and facing an octagonal courtyard. One of the grandest pre-Renaissance buildings in Italy, it is a pillaged Xanadu, once badged with jewels and stocked with fancy sculpture.

Nobody knows what it was built for. Who would choose to live in rooms so ill lit (each has only one tight window)? It had no servants’ quarters and no facilities for a defensive garrison. Ingenious crackpots have given it zodiacal significance as the midpoint between the Great Pyramid and Stonehenge, but it looks like pure three-dimensional swank. I suspect that Frederick — whose later nickname was “Stupor Mundi”, Wonder of the World — was creating a mausoleum for his boyhood inferiority complex.

It’s worth spending a night in Trani, a fishing port one size too big to be adorable, in order to feast at its unusually good restaurant, La Giara, where, for £35 a head, we were supplied with a suite of fish dishes, including the most delicious (and most alarming-looking) squid I have ever tasted. There is no shortage of good produce, especially vegetables, in Puglia, but its most common pasta, maltagliata (“rough-cut”), is emblematic of its menus.

Trani’s romanesque cathedral is an elegant triple-decker sandwich, with a soaring, honey-coloured tower daringly built over an arched base. The bottom of the triplet is the early Christian crypt of San Leucio.

Times recommends

• Six coastal walks to clear your head
• Skiing in Chamonix (behind a horse)
• BA strikes Q&A: how your flight is affected