I would never have discovered Troyes, a beautiful medieval town of timber-framed buildings, were it not for a pale, lumpy sausage made from pigs’ intestines that smells like a pissoir.

To historians, Troyes may be the ancient capital of Champagne, but to food lovers, it is the spiritual home of the andouillette. The champagne cork-shaped town in the department of Aube has been linked with the mal-odorous sausage since the year 877, when Louis II was crowned King of France in Troyes cathedral and the whole town feasted on andouillettes in celebration.

By 1475, the town’s charcutiers had formed guilds devoted to preserving their craft, and the fame of the andouillette grew. Everyone who passed through Troyes, from Louis XIV in 1650 to Emperor Napoleon I in 1805, stopped for a tasting. There is even a fan club, formalised in 1976 by a group of andouillette lovers and food critics to protect its standards and preserve its status. Known as the Association amicale des amateurs d’andouillette authentique, the “Five A’s” has become a symbol of excellence, found on the menus of the most discriminating bistros throughout France.

Outside France, not everyone is a fan. Even the fearless Hugh Fearnley-Whittingstall of River Cottage calls it “challenging”. “I can’t stand andouillette,” says one well-travelled friend when she hears of my pilgrimage to Troyes. “It really, genuinely, stinks.” Yes, it does. To eat it, your eyes, hands and mouth must override your brain, which sends out frantic signals and alarm bells. But if you can triumph over your nose, then your palate will be amazed at the milky, nutty, sweet and savoury complexity of this king of sausages.

A Rough Guide: the best of France

To celebrate its 25th anniversary, the publisher has produced a series of 25 guides to great travel

• Rough Guides: best of Italy

• Rough Guides: best of Spain

BACKGROUND

• The best new French holiday ideas

• Provence’s best kept secret

• A smooth family holiday in Corsica

• Bopping babies in St Emilion

• Having a boule in Provence

BACKGROUND

• Smelly Champagne sausages

• A smooth family holiday in Corsica

Related Internet Links

• Peregrine's France: the Sunday Times francophile reveals all

To uncover the finest andouillette in Troyes is as gruelling a task as finding the best Guinness in Dublin. First, I visit an enormous factory in the industrial backblocks, where the Gilbert Lemelle company manufactures a staggering 20 million andouillettes a year. Now run by bon vivant and rugby fan Dominique Lemelle, it produces a limited number by hand, deemed worthy of AAAAA status.

From him, I learn that the true andouillette de Troyes is pure pork, with only white wine, onions, salt and pepper added. The finished sausages are slowly poached for up to six hours in an aromatic stock. “It’s like Coca-Cola,” says Monsieur Demelle. “You must stay true to the original recipe.”

At the other end of the scale is charcutier Christophe Thierry, who handcrafts his andouillettes in a spotless workroom behind his little charcuterie in suburban Troyes.

Thierry’s output is a more modest 600 andouillettes a day, and it is here, speaking of internal organs, that I lose my heart. I watch as he meticulously cuts the stomach and intestine from organically fed Brit-tany pigs into dangly little strips like so many rubber bands, which he scoops up and loops over a piece of cord. Then with the sleight-of-hand of a magician, he somehow doubles them back on themselves and threads the lot through a sheaf of pig gut, tucking in the ends to form perfect little dimples. I break into spontaneous applause.

But it’s time to eat, which means it is also time to decide how and where to eat. At the pretty little Au Jardin Gourmand restaurant, owner Jacques Lebois presents Monsieur Thierry’s AAAAA andouillettes in a dozen different ways; poached in Champagne, served with foie gras, or with a rich sauce made from the soft, creamy local cheese, Chaource.

To be honest, I barely notice the distinctive smell as I cut through the skin and the labyrinthine bibs and bobs inside tumbleout.Matched with a bottle of the local Rosé de Riceys, it is a wonderfully warming and restorative eating experience.

My andouillette the next day is even better, taken at the cosy wine bar Aux Crieurs de Vin in the heart of town. Simply grilled, and served with a mountain of potato purée, a pot of mustard, and a flute of the fine local Drappier Champagne, it makes me feel strong, ready for the worst that winter can bring.

By pursuing the andouillette, I have opened a door otherwise closed. Much more than a smelly sausage, it is a symbol of the great French tradition of charcuterie and of “making-do”; the perfect mix of French pragmatism and savoir-faire. I have also accidentally stumbled across a fascinating little corner of France that demands a revisit.

We travel for all sorts of reasons – for business, pleasure, in search of culture or just getting away – but we could do far worse, and get more of the flavour of each place, by travelling in search of the great dishes of the world.

The specials

Four other great winter dishes

Cassoulet A dish of white beans, pork, sausages, vegetables and duck or goose confit, sealed with breadcrumbs and baked. Where to eat it: Restaurant Comte Roger, 14 rue St Louis, Carcassonne. (00 33 4 68 11 93 40, www. comteroger.com).

Onion soup gratinée Traditionally used as a restorative after a night’s drinking. Sweet onions are cooked until soft in a meaty broth and topped with bread and melting cheese. Where to eat it: Brasserie Balzar, 49 rue des Ecoles, Paris (00 33 1 43 54 13 67, www.flobrasseries.com ).

Coq au vin A darkly serious chicken fricassée cooked in the red wine of Burgundy, with onions, mushrooms and lardons of bacon, thickened with rooster blood. Where to eat it: Le Chabrot, 36 rue Monge, Dijon (00 33 3 80 30 69 61).

Choucroute garni Sauerkraut (fermented white cabbage) piled high with knackwurst sausages, potatoes and pork knuckle. Where to eat it: Zuem Strissel, 5 Place de la Grand Boucherie, Strasbourg (00 33 3 88 32 14 73, www.strissel.fr).

Need to know

Stay Le Relais Saint-Jean, 51 rue Paillot-de-Montabert, (00 33 3 25 73 89 90, www.relais-st-jean.com). In the heart of the old town, a warm and welcoming family-run hotel with underground car park.
Eat Au Jardin Gourmand, 31 rue Paillot de Montabert (00 33 3 25 73 36 13). Aux Crieurs de Vin, 4 place Jean Jaurès(00 33 3 25 40 01 01).
Buy Andouillette to take home, from Charcuterie Thierry, 73 avenue Général Galliéni, Sainte Savine (00 33 3 25 79 08 74).
Getting there London St Pancras to Troyes (via Paris) starts at £79 return through Rail Europe (0870 8304862, www.raileurope.co.uk).
Further information France Information Line (0906 8244123/60p a min, www.franceguide.com); www.tourism-troyes.com; www.aube-champagne.com; www.tourisme-champagne-ardenne.com

Times recommends

• 'New York has lost its edge'
• The UK and Ireland's 25 best Christmas events
• Chalet Chef 2010: the winners