The metal door to the synagogue swung open and a small boy skipped across the courtyard. He looked puzzled at the three people who stood before him, two of whom were clearly not Iranian. He led us up some steps to the temple, where I slipped a skullcap on to my head. A lady came towards us, smiling. “Are you Jewish?” she asked.

“No,” I replied. “Sorry.”

My friend Annette and I went inside anyway, past a table of food laid out for Passover, and sat at the back as an elderly man read from the Torah in front of eight others.

I'd never have guessed that my first time inside a synagogue would be in Tehran, but Iran is full of surprises. It has a fundamentalist leadership that many in the West believe to be as nutty as a box of pistachios. But it also has a population of 65 million, most born after the 1979 Islamic Revolution (which culminated in the return from exile of Ayatollah Khomeini 30 years ago this month), and far removed from the dour and menacing stereotype often portrayed on the 10 o'clock news. The ordinary Iranian people are by far the friendliest and most welcoming I've met in more than 20 years of travelling.

Flying to and around Iran

Paul Tompkins wants to know who to fly with and whether internal flights are cheap

• Skiing takes off in Iran

Related Internet Links

• More travel articles about the Middle East

Related Links

• Flying to and around Iran

• Skiing takes off in Iran

Our ten-day trip took us from traffic-snarled Tehran 600km (370 miles) south across the Zagros Mountains to Shiraz and the magnificent ruins at Persepolis, started by Darius I in 515BC and destroyed by Alexander the Great in 330BC. (I have never been to a historical site where the past felt so approachable.)

Then we headed back north to the capital via Esfahan and the holy city of Qom, passing near the controversial nuclear facility at Natanz, which looked more like a car assembly plant. I assume, though, that most car factories aren't protected by banks of anti-aircraft guns.

Our guide for the journey was the ever-smiling Mr Sassan, a font of knowledge and always ready with a new story. At the start of the trip I believed all he told me, but as the week got longer his tales got decidedly taller.

We learnt that it paid to sit down when he started to talk, for with Mr Sassan there was no such thing as a quick skip through 3,000 years of history and the conspiratorial goings-on as empires rose and fell, invaders came and went.

“Now this is a sad one,” he'd say before recounting a tale of humble beginnings, love, jealousy, power, betrayal, exile and death. And when we seemed incredulous he'd look slightly hurt. “No, it's true, I'm telling you,” he'd reply. He was also adept at scooping handfuls of nuts and fruit for us from displays in open-fronted shops, walking away waving his cane shouting “Free samples, they don't mind,” as we scurried off. He was also a Mr Fixit.

In Shiraz, after guiding us to the tombs of the classical poets Sa'di and Hafez - as Shakespeare is to us, so are these to Iranians - he tracked down the best local faludeh, a wonderful frozen dessert flavoured with rose water.

The Mausoleum of Shah-e Cheragh has supposedly been closed to non-Muslims for the past three years, since a mullah objected to the revealing outfits of some Spaniards, so we headed through a winding, covered bazaar to its back entrance for a peek through the gates.

Yet, rather than shooing us away, a young caretaker welcomed us inside on the proviso that Annette put on a chador (an enormous cloth that covered her from top to toe) and that we didn't go inside the main shrine.

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?