Bolivians had little time for Che when he was alive. Now you can't turn a corner without seeing his image. Yet, they haven't exactly capitalised on the fact that he died there. The comedian Mark Steel picked up Che's trail in the dusty towns where he spent his final days

To make one of the programmes for the new series of The Mark Steel Lectures, a group of us visited the area in Bolivia where Che spent his final few weeks. Bolivia isn't a major tourist destination. Apart from the armoury of injections, tablets and repellents you are advised to use just to survive the trip (and then there's the kidnapping to avoid too), it's one of the poorest countries in the world; there are few paved roads and until recently it was ruled by military regimes, including the one Che wanted to overthrow.

Our first stop was Samaipata, a town dominated by dust and mountains. Almost any movement on the potholed roads creates a puff of dust like orange talcum powder, so as a distant figure approaches through the haze they look like a stranger coming into town in a Western. Samaipata was the scene of a major battle for Che's brigade. Their plan was to take over the local barracks, and from there launch an attack on the chemists, where they could grab a box of inhalers as Che had run out and was suffering from asthma. The raid was a success, until they returned to their camp and realised that they'd left the inhalers back at the barracks. There's an endearing absent-mindedness throughout Che's campaign, and you imagine that most of his manoeuvres must have ended with a guerrilla holding a grenade muttering: "Now what did I come in here for?"

The chemists is now a private house, but as we were filming outside, a wonderfully South American man in a dark beret, slightly hunched and smiling through deeply engraved creases on his face, emerged through the dust to explain excitedly how he remembered the whole incident, and had subsequently sprayed graffiti in support of Che around the town. He had with him a bag full of newspaper cuttings from the time, and was so enthusiastic he ended up playing a part in the programme.

Three hours up the road is Vallegrande, where Che's body was taken following his execution. But it must have been a bumpy ride because there are no roads at all. There are spaces where roads could be, but they're full of mud, so the place looks like Glastonbury in a rainy year, with stone huts instead of tents. Inside these houses are the most basic items: a table, a small television, a wonky picture of Our Lady - in one of the most sparse of all was a full-size pool table.

The instinct, as a Western tourist in a poor area, is to be wary, but for whatever reason the town of Vallegrande is populated by the most hospitable people in the world. For example, one evening I wandered across the mud in search of a bar, and found a romantic-looking place in which four men were drinking and playing cards by candlelight. I walked in, stood at the table and waited to be served, and asked someone for a beer. She looked a bit confused, and gradually I realised this wasn't a bar at all but someone's house. At which point these people offered me a beer and a seat, and started talking with great delight about Che Guevara. I might try doing a similar thing next time I'm in Croydon.

With a similar attitude, the local population eagerly played parts in our programme. About 50 people flocked into a courtyard to play a chanting crowd. And for one sketch, portraying Che's final arrest, the producer approached a military policeman to see if he fancied playing Che's captor. "Of course," he beamed, "but to make it seem real please wait while I get my best gun."

From then on, it seemed natural to ask Bolivians to be in as much of the programme as possible. For example, the defining moment of Che's radicalisation came when he was in Guatemala, which had elected a radical government. The Americans declared that this proved "for Guatemala, democracy is unrealistic", and they bombed it, replacing the elected president with their own man, who as well as being a supporter of the US was a furniture salesman. So we asked the man who ran the local furniture shop if he would play the part of this dictator, by making a speech that began: "My fellow Guatemalans, as your new President I promise you stability, prosperity - and top-range fixtures and fittings at knock-down prices you won't believe!" With infectious joy, our man launched into his role, imparting a perfect mix of presidential sobriety and cheap TV advert tackiness.

The legacy of Che's time in the country is evident from the murals and posters displaying his image. But they're not brandished Soviet style; they're tucked away. In a tiny photocopying shop behind the counter, in one corner was a slightly torn and lopsided poster. The irony is that when Che was shot there was little sympathy or interest, but now his connection to Bolivia is taken by many as an inspiration. When the government recently tried to sell off supplies of gas and water to American companies, it provoked mass protests, resulting in the multinationals withdrawing and the president resigning. And the most dominant image among the protesters was that of Che.

And Che certainly made a mark on the Santa Cruz bar, on the main square in Vallegrande. In one corner, each night a television shows videos of the protests that forced the president's departure. And on every wall is a huge painting of Che. One depicts him in combat gear, another with his family, but the most domineering sees him lying saintly on his Vallegrande deathbed. In case there's any ambiguity about the message, leaning over the bed is Jesus on the cross.

This is a common theme, with many Che figures accompanied by crosses and images of Jesus. It's a trend encouraged by the Cubans themselves, when they amended the number of followers he'd been captured with, from 14 to 12, to assist the biblical image. And much of Che's life fits neatly into this process, to help the parallels. Just like Jesus, he had a deep sense of commitment to the poor, an obsession with self-discipline, the charisma to attract a devoted following and he was murdered by the state. The trouble is, just like Jesus, his mother wasn't a virgin, he never walked on water and he didn't rise from the dead.

Vallegrande boasts a few Che-related tourist attractions, including his grave and a museum. They're all free and certainly haven't succumbed to modern trends, or set up a "Che Experience" in which you can sit in a "guerrilla simulator". Quite the opposite, at the local hospital, behind a wall and up a path is a shed which houses the actual hospital sink on which Che's body was placed. Carved into the walls are thousands of messages, pledging to honour his spirit. And that's it. Possibly the humblest tourist attraction in the world, and for that reason disarmingly poignant.

Che's standing is such that in shops you find a collecting tin "to raise funds for a Che Guevara airport". This raises two questions: firstly whether you can pay for an airport from donations in shops, but also whether you'd want to travel from an airport named after Che Guevara. Presumably the security staff would ask whether you'd been in contact with anything explosive before packing your bags, and if you said no they wouldn't let you on the plane.

Part of the aura that surrounds him flows from the manner in which he came to be in Bolivia at all. Having helped to lead a guerrilla army in Cuba to overthrow a mafia-backed tyranny, he became the minister for industry, and then set off on his global guerrilla tour. Whatever your politics, you have to acknowledge that for a cabinet minister to disappear to fight in the jungle marks an interesting career move. But his foreign campaigns were disastrous. In Bolivia he attracted little support, his diaries betraying a tragic tale of ineffectiveness. One entry reads: "The march today went well, except for the accident that cost Benjamin his life."

But however hopeless, they were matched by the efforts of the CIA to puzzle where he was. One typical CIA report said: "We can be certain he is either in a) Vietnam b) Algeria or c) Latin America." The FBI reported:

To make the trip, we had to visit a BBC doctor for jabs. A joyful woman prepared a series of needles, with an emphatic "lovely" after each one. "Now, these are for diphtheria, dengue fever, leprosy and typhoid, so that's lovely. Then there's three more for rabies, but you'll take tablets for malaria, lovely. But that's no guarantee you won't catch it. Goodness me, there's not much malaria in Bolivia, except for the area you're going to which is rather riddled with it, so that's lovely. And don't get bitten by sand flies because those little blighters eat your eyes from the inside." "Che Guevara died trying to invade the Dominican Republic. " Then they reported he was in Zambia, Argentina, Colombia, that he'd been murdered by the Russians and that he'd died in a fight with Fidel Castro. At one point the CIA said: "Che Guevara, former Cuban minister of industry, was killed in a miniature yellow submarine." Eventually, in 1968 they tracked him down to the tiny village of La Higuera.

On the map it looks so close to Vallegrande. But getting there entails a three-hour bus journey across mountains. The word "breathtaking" is a miserably lazy cliché, but these mountains are breathtaking. You stand on the edge of the road, condors circling above, try to take in the enormity of these things and literally gulp. And there's nothing and no one as far as you can see, and when there is it's La Higuera, which consists of nine farmhouses, no electricity and two statues of Che Guevara.

For anyone travelling there, accommodation amounts to a tent, or sleeping in one of two huts provided by a French woman who moved there eight years ago, attracted by the Che story. The whole village is about 300 yards long, and at any one time at least one pair of pigs is fornicating in the road.

In the evening, strolling through utter darkness we approached the sound of revelry, and by candlelight found a party taking place in a tiny room. Two children were asleep on a bare wooden bed, while adults passed round a beaker of a murky orange liquid. The six partying peasants owned seven teeth between them, all 12 of their eyes pointed in different directions and one of them beckoned me in, thrust the beaker in my hand and said: " Yaheeugh bara bara fezhhhh ykkkkrama HA HA HA." So I sipped the liquid, which tasted of scrumpy, Domestos and Polish sausage. "Avrezhhhyakayaka, " said my new friend with glee, which must be La Higueran for "Go on, have more than that you fairy". After a few more sips I thought: "Oo I could quite get a taste for this." The peasants obviously did have a taste for it, and held each other up until one collapsed and the rest fell on him in a heap.

La Higuera is described in the Bolivians' own tour guide as "a miserable little hamlet". But they're wrong, because the combination of its remoteness and its place in history is unique and compelling. But don't stay for more than one night or you'll go mental.

The next day we filmed one of our final sketches. Che wrote in his diary that most of his time as a guerrilla was spent sat in a swamp, bored and uncomfortable, and he seemed to be describing the atmosphere on I'm a Celebrity ... Get Me Out of Here!. So we set up a scene in which Che and Castro were contestants on the programme, and went in search of bugs that would be part of Castro's "task". But there weren't any. So we lowered our ambition to worms, but couldn't find a single one. Back when we were dispatched with warnings of deadlines, it would have seemed inconceivable that the only disappointing moment would involve us scouring the countryside unable to find so much as a bloody earwig.

And instead of kidnapping we received a universally joyful welcome. It was a sentiment that seemed all the more poignant when, a few days after our return, Eva Morales, radical opponent of George Bush, won a stunning victory to become Bolivia's president. How they must have cheered that night, so many of the characters we'd met.

We arrived at the five-star hotel, booked to provide relief from the trials of austerity. There was a pool with a dozen water slides, 15 separate buffets and a band with a Casio keyboard. And every one of us felt utterly depressed, wishing we were back up a beautiful mountain with no bugs and the splendid people of Bolivia.

'The Mark Steel Lectures' is on at 11pm Thursdays on BBC4. Sunvil Latin America (020-8758 4774; uk) offers 14-night trips to Bolivia from £2,450, including flights, transfers, b&b and excursions

My favourite hosts

My favourite hosts

Amid the dusty stone houses in Samaipata was the farm at which we stayed, pictured above. It is run by two Dutch hippies in their 50s, whoare enthusiastic about everything. "Are there any snakes here?" asked the producer. "Aah, you want to see snakes, come with me," said Peter, misunderstanding completely. One day he waved his arms excitedly and said: "Aha, tonight there will be very much rain. I can feel it, maybe the roads will be waterlogged, hmmm." And, caught up in his enthusiasm, you found yourself thinking: "Oh brilliant."

Radical departures: Che On Tour

Birth of a guerrilla

Che was born into a wealthy family in Rosario, Argentina, in 1928, the eldest of five. His birthday, 14 June, is disputed. Some say he it was 14 May but that the date was changed to hide the fact that his mother was pregnant before marriage. Visit his birthplace at Calle de Entre Rios 480.

On his bike

While studying medicine at the University of Buenos Aires, Che took time out to travel around Latin America. One of his first stops was Valparaiso in Chile. In his 'Motorcycle Diaries' he describes the huge impact that meeting the poor there had upon his political consciousness.

A changed man

After he qualified as a doctor, Che headed for Guatemala City. He was there in 1954 when a US-backed coup toppled the reformist government for trying to nationalise the US-owned fruit companies. The experience radicalised him, and many other young activists, further.

Enter Castro

In 1955, Che moved to Mexico City with his wife, Hilda Gadea, and worked as a doctor. There he met Fidel Castro and joined the 26th of July Movement. Che was not the only revolutionary to visit this city. It's also the place where Trotsky went into exile and spent the last years of his life.

Batista derailed

In 1958 Che led the attack on Santa Clara. Using a bulldozer, he destroyed railroad tracks, derailing a train full of Batista's troops in a decisive battle in the Cuban revolution. Santa Clara is home to a mausoleum that houses the remains of Che and 16 of his fellow combatants.

Trail of shrines

Bolivia has its own Che trail. The route runs between Sucre and Santa Cruz and the sites include Che's guerrilla camp, the school at La Higuera where he was captured and killed and Vallegrande, where his corpse was put on display.

Rebecca Boellinger