In a striking hilltop position, with views over land and sea, stand the remains of an ancient temple.

Built of yellow limestone, it glows in the sun. Its raised forecourt leads into a central aisle flanked by semicircular apses, altars, carved bowls and faint remembrances of decorative reliefs.

This is thought to be among the oldest buildings in the world - constructed a thousand years before the Pyramids and long before Stonehenge. It is not in Egypt or Greece or anywhere in the Middle East, but in Malta. This little country of sun and package holidays has more to offer than just relaxing by the pool.

The stone in front of me stands 6m (20ft) high and 4m wide and weighs more than 50 tonnes. It is part of the megalithic wall, once up to 16m high, that surrounded the temple complex.

Malta serves up a feast for the eyes and the palate

Culture vultures and foodies will find plenty to their taste

To Ethiopia, in search of The Ark

Patrick Richardson heads to Ethiopia in search of the Ark of the Covenant

• Ethiopia: what it holds for the adventurous tourist

• A guiding hand in Ethiopia

Ephesus: divine inspiration in Greece

The sacred statues of ancient Ephesus exert their power over visitors even in the present day

• 10 classic Greek Island tales

• The perfect Greek island

• Looking for Odysseus on Cephalonia

Uncovering northern Cyprus

Nick Redmayne is enthralled by the sights, cafe culture and people of the less-visited Turkish sector

• Peace at last in rural Cyprus

• High on a Cyprus hill was the family goat herd . . .

• Mighty Aphrodite

Related Links

• Malta serves up a feast for the eyes and the palate

Such massive building blocks earned the temple its name - Ggantija - and the legend that it was built by giants. In reality it was constructed by a society of settled farmers who colonised Malta about 7,000 years ago, beginning to build in stone about 3,500BC.

Substantial remains can still be seen at Ggantija on Gozo, a 20-minute ferry ride from the main island, and on Malta at Mnajda and Hagar Qim - both reopening this summer after the addition of a protective canopy - as well as Tarxien, near the capital, Valletta. All are Unesco World Heritage Sites.

Tarxien is in a rather uninspiring urban setting, but it is worth a visit to put in context some of the best temple carvings that have been moved from here to the National Museum of Archaeology. The museum is in the centre of historic Valletta, a wonderful place to wander under delightful overhanging balconies, with glimpses of the sea popping up at the end of almost every road.

The buildings are mostly of the same warm local limestone used by the temple builders and many date from the time of the Knights of Malta. The museum occupies one of the finest, the Baroque Auberge (grand hostel) of the Knights of Provence, built in 1571. Step inside, though, and you go back much farther than the 16th century.

In the museum's neolithic galleries you can see what Malta's prehistoric temples would have looked like, with lintels and altars decorated with spiral patterns, pitted dots, red ochre and reliefs of plants and animals. A procession of sheep parades along a Tarxien frieze and a Nemo-like fish flounders on a stone block. Of the statues, the most intriguing are the “Fat Ladies of Malta”, generously proportioned female figures with vast bottoms and fringed skirts. A guide pointed out that until 20 years ago it was considered healthy and feminine for a Maltese woman to appear rounded and well-fed.

Behind a door in the middle of a suburban street lies the extraordinary prehistoric site of the Hal Saflieni Hypogeum, a 5,000-year-old underground necropolis carved out of solid rock. Recently restored by Unesco, the labyrinth of passageways and chambers is carefully conserved with low lighting, and visitor numbers limited to ten an hour. This adds to the atmosphere, making it easier to imagine the time when funeral parties brought the bones of their compatriots to rest here.

Armed with an audioguide, we descend along metal walkways into the subterranean darkness. In a couple of chambers red ochre spirals and honeycomb patterns still decorate the walls. When we reach the “Holy of Holies” there is a sharp intake of breath. It is almost like time travel, staring at an ancient temple 10m underground. This is unique. Lying by the pool can wait.

Need to know

Getting there

Air Malta, BA, Ryanair and easyJet fly to Malta from Heathrow, Gatwick, Manchester, Birmingham, Glasgow and Luton.

Buses and taxis run all over the island. Malta Tourism Authority (020-8877 6990, www.visitmalta.com)

Further information

Details for entry to temples and museums at www.heritagemalta.org. Book the Hypogeum in advance

Reading Malta: Prehistory and Temples, by David H.Trump and Dan Cilia, available from www.amazon.com

Times recommends

• Dubai cheaper than Doncaster as room rates tumble
• World Cup 2010 - how to follow England
• Copenhagen: Europe's greenest city