The genesis of the New Europe series was the same as most of the journeys we have done. Basically, when one is finished, I swear I will never do another. It is a fairly exhausting process and immediately afterwards is not the time to even think about another one. But once the programmes have been shown, the publicity done, the dust settled – say, a year later – the idea doesn’t sound so bad. But it’s not just up to me. We have grown into a team, a family, almost, and if one of the key members of the crew, like Nigel the cameraman, said no, I think I might jack it all in. But inevitably someone says: “Shall we do another?” And, being rather weak-willed – and still enjoying travelling – I say, well, let’s think about it. However, one of the things that is crucial to the enterprise is that we have to find somewhere that excites and interests me and the others. It must be genuine enthusiasm. It can’t feel like we’ve said: “Oh, let’s just go out and knock one off.”

There was talk of South America, and particularly Brazil and Argentina, which I have never been to. But I had visited the continent in Full Circle, so it had a slight feeling of covering old ground. Also, my first grandchild had just been born, and I wasn’t sure I wanted to be quite so far away. Like any of us, I can be caught by homesickness, although having the crew around helps when it strikes. Then someone suggested Europe, but the thought of covering well-trodden Paris or Madrid didn’t inspire me, until we considered eastern Europe, or New Europe as we ended up calling it.

I realised I had flown over it many, many times, but I knew less about what had been the old communist countries than I did about Hong Kong or Africa. I also felt that we shouldn’t do another landscape series. I think I’ve run out of superlatives to describe sunsets or mountain ranges. Not that we didn’t discover beautiful or strange scenery, such as the Jura mountains and Cappadocia, but this series was going to be more about people. Plus I wanted to try to demonstrate these countries weren’t all drab and monochrome grey, that colour didn’t end at the old Iron Curtain, and that not everyone in eastern Europe wanted to leave and come here.

One of the things that concerned me most before we left was the quantity of drinking I might have to do. I knew that everywhere we were going, the locals have their own brandy, rakija, raki and wine they would want us to share. I am not very good with spirits, or perhaps vice versa. Luckily, the crew, being pros, don’t eat or drink while they are working, but, being pros, eat and drink a lot when they’re not. So I was always able to say, we have to get back to the hotel so the crew can have something to eat and drink. It is a convenient get-out when hospitality threatens to overwhelm, especially if plum brandy is involved.

Then again, we found some marvellous wines, particularly in Moldova, Bulgaria and Romania. Before, under communism, it was all about quantity, not quality. Maybe not for the best brandies, because they were for the elite, but certainly winemakers were not encouraged to take time and trouble, just to produce something alcoholic. Now they are making great progress, and some of the bottles from areas you wouldn’t even consider buying at home were excellent. Mind you, some weren’t.

We went through some 20 countries, including Lithuania, Latvia, the Czech Republic, Hungary, the various states of the old Yugoslavia, Estonia and so on, but I was probably most taken taken with Moldova. It’s intriguing because it’s a small country about which you rarely hear. But to go there and find it has an identity of its own was quite rewarding. I knew it was an ex-Soviet satellite, and I expected it to be pretty grim, but the capital, Chisinau, is a fine city, very green, built on a human scale, not full of drab concrete blocks or triumphalist wide boulevards. They leave that to Transdniester, Moldova’s own breakaway republic, which is a last bastion of communist triumphalism. So Chisinau was very nice, although the hotel wasn’t great. As I wrote in my diary at the time, when I requested toast, it was as if I’d asked them to get a child off the street and roast it for me.

The service industry might still be taking its first faltering steps, but the people we met in Moldova were very good indeed. Tatiana, a local journalist who also works for Unicef, took me into the park, where there was a bandstand with a proper band and all these sweet old couples dancing. She felt her childhood had been safe and cosseted under the Soviet system, and seeing the dancing couples brought it all back. Not the system, but the sense of security. Many of the old people felt the same: they liked the new freedoms, but missed the jobs and the pensions.

I also enjoyed Croatia, which seems to me part of Europe already. It’s slotted in very well. And it had some of the best food – the fish restaurants on the Dalmatian coast are wonderful. Serbia seemed trickier, more isolated, as if it didn’t quite know where its future lay, where it quite fitted into Europe. Plus, they couldn’t understand why quite so many people seem to hate them. Yet we met some lovely Serbs, and Belgrade is a good-time party city, and stayed that way even when it was bombed.

That was a sensitive subject – because it was us who did it – but you can’t go to eastern Europe without visiting a concentration camp or considering the legacy of ethnic cleansing. It can’t all be the lighter things, such as Turkish oil wrestling, belly dancing or the actor who makes his living playing Dracula in Transylvania. You have to strike a balance.

One of the great experiences of the trip was in Poznan, Poland, where they let me drive a steam train. This is something that would never, ever happen in this country. They allow someone who has never driven before – the most I’ve done is stand on the footplate – take a commercial service with passengers on board through the forests at 50mph. These are people who want to get from Poznan to Wolsztyn on time and alive. An English steam nut called Howard Jones has set it up so that any train enthusiast can go out and take lessons. Even a Python. I was very nervous at first, particularly as I knew we had only one take at it – we could hardly back the train up to try again.

The driver, Jani, was a man of few words, and fewer still in English, which didn’t help. But, after a frantic period, once everything is in place there isn’t much to do in the middle part of the journey, except look out for crossings and, eventually, stop. And that’s what buffers are for, aren’t they? So I really enjoyed it. When we got back, I looked at the wide shot of the train puffing along at what seemed a fair old speed and thought, that’s me driving that. It is quite a physical effort to drive a steam train and bring it to a halt, and I got off happy, dirty and slightly trembling.

If I could choose only one memory from New Europe, it would be a moment with an echo of the Pythons, featuring another train, this one full of lumberjacks in Romania. Every morning, an old 1954 locomotive pulls these rickety carriages of woodcutters up into the high forest of the Maramures mountains. It was a beautiful day – freezing cold, but the cameraman got some wonderful shots as the sun came over the peaks and down the mountainside to reach us.

The lumberjacks play cards and drink beer and tuica, a local moonshine made from plums. No wonder some of them were missing fingers. I made a note to stand well back when they were chopping. When some got off at the intermediate stops and greeted their waiting friends, they did so by grabbing the crotch and lifting their companion into the air. So I was quite nervous when we disembarked at journey’s end, but the people who welcomed us there seemed happy with a handshake. The track is 26 miles long and, when the lumber trucks aren’t running, very quiet. It just felt like a special, remote, inaccessible part of the world.

I finished the journey by taking a beautiful old DC-3 from Tempelhof, in Berlin, to see Hitler’s “people’s holiday camp” on Rügen island, in the Baltic Sea. That was a strange feeling. In a propeller plane of that vintage, it almost felt as if we were going to bomb it. The development at Prora – three miles of five-storey accommodation – never did serve as a holiday camp, but became a hospital for evacuees and barracks for slave labour. Now it is an eerie, dusty, white skeleton, a deserted monument to the old Europe, the one that did things by force. Yet there, at the end of travelling through those 20 countries for five months – over a period of a year – I did feel that I had seen a New Europe, that we’d brought home a snapshot of part of the world at a crucial tipping point. For the first time in a thousand years, it’s possible its future will be decided by consensus and cooperation rather than bloody conflict. Let’s hope so, anyway.

His latest series, New Europe, begins on Sunday, September 16, on BBC1. His book New Europe (Weidenfeld & Nicolson £20), with pictures by Basil Pao, is out on Thursday. To buy it for £18, with free p&p in the UK, call The Sunday Times BooksFirst on 0870 165 8585

Times recommends

• Croatia: the flashing blades of Korkcula
• The best stopovers en route to Australia
• Chernobyl offers a holiday in hell