My transport arrangements wouldn’t be to everybody’s taste, but they’ve certainly been colourful. Here I was, squashed in the back of an ageing taxi, squeezed between unshaven, turbanned men with daggers in one pocket and apricots and almonds in the other. As we bounced through the mountains they fed me filthy handfuls of the fruit and nuts. I tried not to think about the daggers.

After a while we turned off the highway and pulled up at the house of the man on my left. We all piled out, the driver included, and our host ushered us in to sit on his richly carpeted floor. A tray of tea was handed round, plates of food appeared from nowhere, and soon a stream of neighbours came in to meet the unexpected and startling British guest. Several of them reminded me, putting their hands to their hearts, how in 1991 John Major helped set up the ‘safe haven’ which ended Saddam Hussein’s campaign of violence against the Kurds. Sir John seems to be almost a national hero here, alongside George Bush Senior and of course the legendary Kurdish freedom fighter Mustafa Barzani. Strange bedfellows indeed.

Under the new Iraqi constitution Kurdistan is now an autonomous region, with its own parliament, army and flag; and it has been steadily rebuilding its shattered towns and villages with the help of truly vast amounts of international investment. With bombings still a real danger in nearby Mosul and Kirkuk, you’d be forgiven for thinking twice before booking your autumn mini-break here. But against all the odds Kurdistan has been almost completely free of violence recently – so much so that American troops in Baghdad often come up for a holiday. As Nimrud Youkhana, the Kurdish Minister of Tourism, has put it, “This part of Iraq is very different from the rest of the country. We have peace, security and a low crime rate. It’s actually safer here than in many parts of Europe.”

An hour or two later I continued my taxi journey through the mountains. I was now on the Hamilton Road, a strategic route into Iran that was commissioned by the British back in the 1920s. It snakes perilously through a sort of mini-Grand Canyon and was to be part of an imperial trunk road to Asia.

Approaching the Iranian border, we were stopped by a young Kurdish soldier who politely asked what I was doing there. “I’m a tourist,” I said – and in a sudden Fawlty Towers moment added, “I don’t do anything.” He led me to a concrete building and went off with my passport. Minutes turned to hours. The taxi disappeared. Other soldiers arrived with kebabs which we all tucked into. Finally, as the last light was fading, a senior officer turned up and said in impeccable English, “I’m so sorry, Mister John. Here’s your passport. We had to check with headquarters. We didn’t know what to do with you.”

Many Kurds speak excellent English. At the height of Saddam’s atrocities some were given asylum in Britain, and now a fair number of these are back in Kurdistan. Down in the plains, in the city of Sulaymaniyah, I was walking through a bazaar when a man called out to me from a butcher’s shop. Was that a Yorkshire accent? It was, and it was saying “Come and have some tea!”

The voice belonged to Asad, recently returned from Leeds where he’d been working as a butcher’s assistant. He’d done well, saved money, and now ran his own shop supplying beef and lamb to Sulaymaniyah’s restaurants. “Do you miss Leeds?” I asked. “Mmm, sometimes,” he said tactfully. “But things are much better here now. I’m back with my family and I’m teaching the business to my little boy.”

But the little boy’s future may not be as secure as Asad would wish. Time and again I’ve seen maps of a ‘greater Kurdistan’, extending from the Mediterranean almost to Baghdad, and including large chunks of Syria, Turkey, Iran and Iraq. A student called Mohamed told me what these maps were all about. “It’s our age-old dream of a proper Kurdistan nation,” he said. “Don’t forget we’re 30 million people – that’s more than most European countries. And we’re hardworking – like the Poles and Germans put together. We want an independent Kurdish state, and if we play our cards right I think we’ll get one within 20 years.”

But in the meantime, is Kurdish tourism about to take off? Well – not just yet I think. Getting around isn’t straightforward; there are still lots of army checkpoints; and unplanned stopovers like the one I had aren’t everyone’s cup of tea. This perhaps explains why I haven’t actually met a single other foreign tourist here. Don’t tell anyone, but they’re missing a treat.