Madrid is, on its surface, the purest essence of unchanging, Catholic Spain; as pure as the all-white shirts worn by David Beckham and his Real Madrid team-mates. Nuns still scuttle between convents; an army garrison broods on the city's main thoroughfare; the king and queen are loved; and two-and-a-half-hour lunch-breaks are standard. In the Plaza de Colon, a huge Spanish flag undulates calmly in the wind. In keeping with this, the menus at the capital's most traditional eating houses differ little from the days of the Armada.

Yet there is an undercurrent of change in the Spanish capital and its food is a fine way to gauge this. The nueva cocina movement has lifted Spain above Britain in international restaurant rankings, and is also evident in a new generation of tapas. This gastronomic innovation is a reflection of the country's growing confidence since the economic boom of the Nineties.

That same confidence means that what was an inward-looking country is also now at ease with the foreign: ideas, immigrants and of course food. Now society is more plural, vegetarianism is no longer seen as a sign of mental imbalance. And there are even the first suggestions of change to the famously conservative Spanish eating etiquette.

The plight of the visiting vegetarian always seemed particularly cruel given the superlative quality and freshness of the vegetables on offer. For those who eschew meat, life was a hell of endless tortilla and careful extraction of bits of ham and tuna from salads. Now at last there are some decent veggie restaurants emerging. Artemisa (Calle Ventura de la Vega, 4; telephone 91 429 5092) [all of the phone numbers given in this article should be preceded by 00 34 if calling from the United Kingdom] has been a successful pioneer, offering more than 50 dishes, though several were blanketed under a weight of cheese when I visited. Healthier, while also tasty, is La Biotika (Amor de Dios, 3; 91 429 0780).

Concerning food from abroad, Madrilenos were once wary of anything except the palest shadow of the authentic. But as the city's population has evolved (one sixth is now foreign-born), so too has the fare.

Take Japanese food, for example. Restaurateurs Eiko Ikenaga and her husband arrived in 1958, when they must have been almost the only Japanese in Spain. 'The city was quiet then, but vegetables were so much cheaper than in Tokyo,' she reminisces. Initially, they had to learn Chinese cookery, since sweet-and-sour was all that diners would order. Now their restaurant Janatomo (Reina, 27; 91 521 5566) serves the real thing, and I particularly recommend the aubergines in miso sauce. A few stops down the Metro, Summa (Profesor Waksman, 5; 91 457 3227) represents the next generation, offering 'Japanese fusion' (a winning example: salmon sashimi with jalapeno sauce).

Culture or carousing may be your primary reason to visit Madrid, but there has never been as good a time for the food that will accompany your stay.

Where to eat

Traditional Spanish cuisine

Madrid's own cooking is the proud cuisine of the Castilian high plains, and often the despair of the visiting vegetarian. The most celebrated dish is cocido Madrileno, a stew that mates chickpeas, potatoes and other vegetables with chicken, pork cuts, and beef. Cocido is poor farmers' food in that it economically produces several courses, starting with its broth and culminating in the meats. A close second is callos, in which a tripe casserole is enlivened with chorizo and chillies. From the mountains just north of the city, there are also roast lamb and suckling pig.

These recipes are food as history. But, as you enjoy them, note that the tradition is not as Spanish and Catholic as it is presented. Cocido probably originated as a Jewish Sabbath dish, with the pork added later by Jews seeking to avoid the Inquisition by showing they had become Christian.

Sobrino de Botin (Cuchilleros, 17; 91 366 4217) is Guinness World Records-affirmed as the world's oldest restaurant. Its original wood-fired oven is worth a glance, though you'll have to take in the shelves racked with recently deceased piglets. An equally substantial rival is Casa Lucio (Cava Baja, 35; 91 365 3252), which has hosted Bill Clinton and Penelope Cruz (separately, the waiter adds).

Food also reflects the nation's current fractious politics. Much of Spain is pushing for more freedom from the capital's yoke. And for a subtle sign of how Madrid has dominated the country, you only have to survey its other traditional restaurants: the best of the catch has been whisked each morning from fishing villages hundreds of miles away on the coast to be served that evening over Madrileno tablecloths. Metropolitan eateries can offer some of the best Galician seafood - try the crab at Ribeira do Mino (Santa Brigida, 1; 91 521 9854); or great Asturian fish - try the fine hake in cider at Casa Lastra (Olivar, 3; 91 369 0837) - and if not appled-out, wash down with luscious cider brandy; or even Valencian paella at La Paella de la Reina (Reina, 39; 91 531 1885).

Few countries have so varied a range of regional cuisines as Spain, and here visitors have a happy opportunity to sample it all within strolling distance.

La nueva cocina

This year Spain overtook the UK in the league of the world's 50 best restaurants, with Catalan Ferran Adria replacing Heston Blumenthal in the number one spot. Most of Spain's new superstar chefs are from Catalonia or the Basque country, but like the imperial city it is, Madrid reels them in.

For an extreme culinary (and financial) experience, diners may pay homage at La Broche (Miguel Angel, 29; 91 399 3437) where Adria-protege Sergi Arola serves up edible foams or avant-garde dishes such as turbot stewed with rooster combs, in a minimalismo all-white space. Santceloni (Castellana, 57; 91 210 8841, closed in August) has a warmer setting and a calmer menu, but chef Santi Santamaria's Michelin stars have been won for excellent freshness and use of ingredients, discernible in the 10-course gastronomic menu or his signature sliced-langostine ravioli.

For a more intimate experience, head for Arce (Augusto Figueroa, 32; 91 522 0440), a gem absent from the main guidebooks, where Basque chef Inaki Camba will sit with you and create a personal menu. No less fancy (we were treated to hake immersed in liquefied jamon iberico), but what a pleasure to be asked by the cook about the structure of your appetite in detail.

If your budget needs close management, there is also a taste of nueva cocina available at Sergi Arola's modestly named Arola-Madrid (Isabel, 52; 91 774 1000). An eccentric menu (starters comprised eight soups and one salad when I visited) is overshadowed by the darkly powerful architecture of Jean Nouvel. Conveniently, Arola-Madrid forms part of the new wing of the Reina Sofia museum, home to much of the work of Picasso, Miro and Dali.

Tapas old and new

The Spanish know what many British don't: that food shouldn't be divorced from drink - thus Spain's biggest culinary export, tapas. In Madrid, a war is currently under way between traditionalists and revolutionaries. The frontline winds along the narrow streets near the Plaza Mayor.

At Cien Vinos (Nuncio, 17, 91 365 4704), the owner Inaki proffers a timbal de couscous, uniting wild mushrooms, paté and caramelised onions with a further nod to Spain's Maghreb heritage. Like many usurper establishments, Cien Vinos combines tapas innovation with cultured wine appreciation and offers an excellent wine list.

The venerable La Chata (Cava Baja, 24, 91 366 1458) counters with a tosta de matrimonio - fresh and smoked anchovies with tomato and tender red peppers somehow representing the bittersweet pleasure of matrimony. The traditionalist clientele here prefer frothy draught Mahou beer.

As tourism swells in Madrid, the custom of foreigners might swing the outcome of this contest. For a neutral tapas tour, try Adventurous Appetites (639 331 073; www.adventurousappetites.com) which offers tailormade walking tours of the city's top tapas establishments for groups of up to six. If you've tried tapas in the UK, it's probably been a dismal version of traditional, and sampling both versions of the real thing in Madrid will be a pleasure.

Where to shop

Every chef knows it: a dish is only as good as its ingredients. The best of the nation's produce is piled high on the shelves of Madrid's many markets.

Silvery mackerel flank smooth crimson peppers and a cornucopia of cheeses at the ornate Art Nouveau Mercado San Miguel (Plaza San Miguel), though it doesn't match the grandeur of Barcelona's La Boqueria.

Aficionados of Spanish ham should seek out one of the surreal Museos del Jamon (Atocha 54; 91 369 2204 and elsewhere) and demand to sample free-range jamon iberico de bellota, washed down with cold beer.

For an expert opinion on olive oil, I had the fortune to meet Alicia Rios, catching her in the middle of a commercial tasting session.

'Mmm, a floral aroma, bitter evolving into sweet, a picante finish - not bad, but it lacks alegria,' she pronounced on a new offering from Extremadura.

Alicia is a renowned olive expert within Spain, which has long been the world's largest olive oil producer. She explains with some passion how the oil acts as 'the perfect absorber and conductor of taste and aroma', counselling the British to use it and other ingredients more intuitively, ending our obedience to recipes. For the best range of oils in Madrid, she recommended the Patrimonio Comunal Olivarero (Mejia Lequerica, 1; 91 308 0505), where manager Pedro supplies, and can knowledgably discuss, 80 brands. Current top of the line is fruity-smooth 2005 estate-bottled Marques de Grinon.

For wild mushrooms, the place to go is the little-known Cisne Azul (Gravina, 19; 91 521 3799). Inside what looks like an old-style bar, Julian Pulido and his two sons serve 15 types of wild fungus, many of which they pick themselves at weekends in Madrid's surrounding mountains.

Eating etiquette

Food is also culture, and visitors will have to adapt their schedule in a city still unconvinced by the work ethic of Barcelona, let alone that of Britain. Breakfasts often feature at 8am and 11am (many office workers take both); the substantial lunches are taken between 2pm and 4.30pm (during which most shops close); the equally substantial dinner won't start before 9pm; but tapas can fill any spaces in between. When indulging in the latter, be warned that three measures exist, with the basic tapa complemented by the smaller pincho and the larger racion

Bar staff tend to be speedier and restaurant staff more glacial than back home. Follow the lead of the locals, but olive stones and napkins may be more welcome on a bar's floor than anywhere else, while cigarette smoke is welcomed almost everywhere. For the most pleasing prices, always ask about the economical menu del dia at lunchtimes.

Those are the fundamentals, but change is starting to happen. Let's start with breakfast. For a century that has meant a stale croissant and good coffee. Now, at the gently lit Mama Ines (Hortaleza, 22; 91 523 2333), there are tostadas spread with tomato, garlic and scrambled egg, accompanied by fresh fruit juices and teas. Or, somewhat less laid-back (including the service), Cafe Oliver (Almirante, 12; 91 521 7379) serves up an extensive brunch for €19.50 every Sunday. Both establishments are in the city's gay-friendly Chueca district.

But of all the changes to eating habits, the most radical may be the arrival of high-quality fast food, as some Madrilenos' lunchtimes are pushed towards a shocking single hour. Nueva cocina godfather Ferran Adria's is characteristically the most ambitious of these new offerings, the appallingly named Fast Good (Juan Bravo, 3C; 91 577 4151 and elsewhere).

Fast Good's service may not actually be that speedy, but it trumps Burger King on decor, ingredients and presentation. The mustard on my pampera burger was wholegrain; my salad included blackberries, almonds, chervil and shallots. This may follow tapas as the next big Spanish culinary export.

Finally, any extended night in Madrid should properly be topped off with thick hot chocolate and churros (doughnut fritters). Best for this ritual is the Chocolateria San Gines (Pasadizo de San Gines, 11; 91 365 6546, open until 7am). With the chocolate brought over from the Americas, and the pourer too judging by his accent, this is one more deceptive 'pure Spanish' tradition to be enjoyed.

Getting there

Dan Whitaker stayed at the elegant Hotel Orfila (www.hotelorfila.com), doubles from £258 a night, and flew to Madrid with BA (www.britishairways.com), return flights from £88 return.