Presenter Michael Palin and film-maker Roger Mills look back on 25 years of globe-trotting

Without the award-winning film-maker Roger Mills, there would never have been a Michael Palin, travel presenter. Here, the duo look back on a decade spent criss-crossing the world - the tiffs, the bungee jumps, the fermented spittle…

As the co-producer of Around the World in 80 Days, Mills (left) had the power to transform Palin's life (Anna Huix)

"Do you remember when you had to drink the old lady's fermented spittle?" Michael Palin is being asked to reminisce on the many discomforting tasks he's been obliged to perform by Roger Mills, the mischief-making Oxford classicist with whom he has travelled the world.

"I didn't know it was the old lady's fermented spittle until we asked what it was – I thought it was rather nice," Palin recalls. It was pink and yoghurt-like, and he quaffed it on the banks of the Urubamba River in Peru. "They were having a celebration. It was a welcoming thing and I couldn't turn it down; it would have been very, very rude. So I drank it."

Aside from having to imbibe the saliva of elderly Peruvians, Palin has many reasons to be grateful to Mills – the man he calls "The Professor". For it was this self-same Roger Mills, a seasoned and much-awarded documentary-maker, who turned the vendor of the Dead Parrot into a real-life Phileas Fogg a quarter of a century ago.

Palin was then at the peak of his 1980s success, but as co-producer of Around the World in 80 Days, Mills had the power to transform his life. Although Palin was one of Britain's most popular comic performers, he was not quite a shoo-in for the new show, which would re-create the fictional itinerary undertaken by Fogg in Jules Verne's 1873 novel of the same name. First, Mills had to dampen the wanderlust of Alan Whicker, then the unrivalled doyen of British travel broadcasting and anointed by BBC bosses for the Phileas role. Fortunately, Mills knew how to dissuade the famously smooth Whicker from taking the gig. "Stress the discomfort of it," he advised co-producer Clem Vallance, who, like Mills, preferred Palin for the job.

Over a lunch with Whicker in London's Kensington, Mills made clear what the job would entail: "Alan," he said, "you will have to share deck space with the crew between Oman and Bombay." From then on, Mills says, "He looked into the middle distance and took no further part in the discussions. He wrote a letter the next day to the effect that he thought the pace of the show would be such that he wouldn't have time to prepare his interviews."

That seven-night, eight-day dhow journey to Bombay – with 18 Gujarati crew but no radio or radar – was the making of Palin as a travel presenter. The audience warmed to the sight of him sleeping under the stars on deck, not to mention relieving himself via the precarious outboard toilet. "Never have I been in a situation where, for so long, I depended upon a group of people quite different from me in wealth, class, race, religion and circumstance," Palin writes in Travelling for Work, the third and latest volume of his diaries.

Palin on the roof of the Nile Valley Express in Pole to Pole (BBC)

As the Python and the Prof come together now to reminisce over that epic journey, first screened 25 years ago in 1989, it is clear how close they became working side by side on all but one of Palin's great television odysseys. At 77, Mills is suffering from Parkinson's and Palin is considerate of his friend's welfare – even if the veteran producer is clutching a clipboard with a sticker reading: "InterContinental Hotel Kinshasa – No Kalashnikovs".

They refer to themselves as "a married couple" and, at one point, Mills rebukes his presenter for the bad temper which viewers would not recognise. "You can get quite grumpy when things aren't going efficiently and you feel people haven't pulled their weight," he says. "You've made me very upset at times, Michael, [although] you've said 'I'm sorry' at the end."

Palin, 71, makes no attempt to deny it. "Everybody who knows me knows that I can be quite sparky and rather rude." Not often, though. In a travel broadcasting career that has now spanned eight adventures, his secret has been his empathy with the people and cultures he encounters. His journeys have never been exotic freak shows, but celebrations of the human spirit in its many forms.

Readers of Travelling for Work may, however, be surprised to discover just how difficult Palin found his new milieu. "The realisation that this whole project is supported on my shoulders and demands not just my survival but my wit, energy, exuberance and enthusiasm quite terrifies me," he records in September 1988, while heading down the Adriatic in the early stages of Around the World in 80 Days. "Failure is unthinkable."

Palin aboard a train in 80 Days Around the World (Basil Pao)

He worries about his diet and his deficiencies in sleep, but most of all he is tormented by self-doubt over his ability to make good documentary television. "There are people much better at this than I am," he writes. He further wonders what some of his peers would have been able to make of the task. I think of seeing all this through Jonathan Miller's and Alan Bennett's and Terry Gilliam's eyes and how much sharper and more original it might all be."

He finds being an "inquisitor" unnatural, admitting that he thinks of the camera as "an embarrassing intrusion", even at the end of the globetrotting journey. "I prefer when I'm travelling to take in what's outside by myself, privately, and I respect the same privacy for other people. This makes it difficult to grab people and interrogate them."

It is as well that he has always had Mills to do some people-grabbing for him, scouring the path ahead for interviewees whom Palin could "encounter", or discovering rituals for him to undergo, such as walking across hot embers in Estonia. "We did terrible things to you, didn't we?" says Mills. "People love to see you suffer; we found that out fairly soon. There's not a Turkish bath or hammam that you haven't been slapped or walloped in – or any medicinal mud that you haven't been smeared with."

Mills was already a Bafta-winning film-maker when he began to work with Palin, and repeatedly told him, "I would never ask you to do anything I wouldn't do myself," which is why he didn't insist on Palin completing a bungee jump in New Zealand. "I was close to it but I wasn't keen on bungee jumping; I could never see the point of it," says the presenter. "It was plunging down to this rocky stream bed below and it was the only thing I said no to."

In a travel broadcasting career that has spanned eight adventures, Palin's secret has been his empathy with the people and cultures he encounters (Anna Huix)

Despite the harsh judgement of Whicker, who called the series "a seven-hour ego trip", Around the World… was a triumph. Perhaps the viewers enjoyed seeing Palin squirm because he's so genial – and so successful. As he fretted over his travel work, he wondered whether it would undermine his acting career, even though A Fish Called Wanda, his Hollywood heist comedy with John Cleese and Jamie Lee Curtis, had recently been a box-office smash. He need not have been concerned: as he returned to London on Around the World…, after an absence of 79 days and seven hours, his "profile at home had never been higher", he noted in one of the Alwych notebooks he used as a diary. k

Indeed, in the decade up to 1998 covered by Travelling for Work, Palin constantly pushed himself as an actor and a writer. He won critical acclaim for his role in Alan Bleasdale's TV drama GBH, wrote and starred in a film, American Friends, started writing a novel, Uganda, and even created a stage play, The Weekend (which was panned by the critics).

As he travelled, family life went on. While he was away filming, his son, William, sat his Oxford exam, and his wife, Helen, underwent surgery for a tumour close to her brain. The diaries also cover the death from cancer in 1989 of Monty Python's Graham Chapman and a Pythons' meeting in London's Camden Town, earlier that year, to discuss a 20th anniversary celebration. Following the rendezvous, Terry Gilliam exclaims: "After today I know we'll never do anything together again." Of course he was proved wrong, eventually – the troupe marked their 45th anniversary this year with the Monty Python Live shows at London's O2 Arena.

In Full Circle, Palin undertook a 50,000 mile trip around the rim of the Pacific Ocean (BBC)

"I was seen – not entirely fairly, but largely fairly – as the one who was wary of doing something in a very, very big auditorium in Las Vegas without Graham and possibly without Terry Gilliam," says Palin. "[But this year] everything just came together. We had the technology to integrate Graham into the show, we had a reason to get together – which was that Python had no money. So we decided to do it unanimously – within five seconds everyone said yes."

The decision was vindicated, he says. "It turned out to be spectacularly right, because we got far more people coming to the shows than we ever expected."

It was not long before that 1989 gathering that Palin and Mills first met, at the Museum Tavern outside the British Museum. Palin gave the documentary producer a dusty travel book, Everywhere, the Memoirs of an Explorer, by Arnold Henry Savage-Landor. Mills produces it now in a central London private club (the Union in Soho, where Palin is a member, rather than the Reform in Pall Mall, from which he and Mills, like Phileas Fogg, departed on their trip round the world).

Mills reads aloud an unlikely excerpt from Savage-Landor's work, in which the author asserts that the Tibetans at the turn of the 20th century were a vicious bunch. "I was torn off my saddle and the instruments of torture were exhibited to me. An angry crowd yelled: 'Kill, kill!'" Mills doesn't believe "a word of it".

The first meeting was the beginning of a long and fruitful working relationship. After Around the World…, the BBC commissioned Palin to continue his travel adventures by following the 30 degree line of longitude in Pole to Pole and then circumnavigating the Pacific in Full Circle, always alongside the Prof.

As genuine as Palin's travel persona appeared to be, Mills was very aware of the benefits of his presenter's acting skills. "I realised very soon that we had a treasure in you because you were an actor – that's what you would have put under profession in your passport. You could do things others couldn't do." When the Orient Express stalled in Austria, for instance, Palin stood on the platform and serenaded the sylvan scene with a rendition of "The Lumberjack Song".

Mills and Palin at the Union club in London's Soho (Anna Huix)

In his diaries, Palin suggested otherwise. "I can act – I can act characters of all sorts till the cows come home – but I can't act me," he agonises. It was during that slow boat to Bombay that he cracked it. "I thought 'I can just be me, there's no point in trying to be an actor or trying to be a reporter or journalist or sociologist – just be me travelling'," he says. "After the dhow, I realised that what I was seeing was interesting and what I was showing the world was absolutely fascinating, so forget about me. That crystallised what became my approach."

Palin talks as if there may be more shows yet; he wants to go to Madagascar, and he also thinks there's a "big gap" in his coverage of the Middle East. But, he claims, the BBC wants to move on, and was reticent to commission more episodes of Brazil with Michael Palin in 2012. "I was a bit bewildered by the [BBC's attitude]," says the presenter, who nonetheless acknowledges that his style of TV travelogue has perhaps had its day. "It's time to have a different format done by different people."

Though that's not to say Palin is terribly keen on the sort of hyped-up modern travel shows which he says have been "influenced by advertising campaigns. There's this feeling you have to tell them the recipe from the start and you end up showing the same clip three times." Having said that, one younger presenter he does admire is Simon Reeve, who has "a nice inquiring eye".

Travel shows or not, Michael Palin will always have options. He looks after himself because he has work to do. Travelling for Work details his enthusiasm for running and clean living, even if he clearly likes his food and references various brewers by name.

Though let's not get too carried away here: "I have never seen him pissed," says Mills, which is no idle boast given he followed him with a camera from dawn till dusk, all over the world. "He's generous, charming and good company – I cannot find fault with this man. Yes, he gets ratty sometimes, but then he's filled with remorse because he feels he has let himself down."

And then, as 25 years before, the pair head out of the private club and back on to the streets of London. This time they take separate paths – though it's pleasing to imagine that their spirits will always be in step.

'Travelling to Work: Diaries 1988-1998' by Michael Palin is out now, published by Weidenfeld & Nicolson, priced £25. Palin’s Travelling to Work tour runs until 22 October; see www.palinstravels.co.uk for further details