Viva a food revolution

Finally we find it: a fisherman's shack on the water's edge where ramshackle boats collect. At this spit-and-sawdust joint they turn the catch of the day into sashimi, nigiri and California rolls. Octopus and fresh fish are on the menu, which isn't written down. It's zingy, delectable and fresh. When friends told me about Paladar de Santiago (240A 3ra. C, Jaimanitas, no phone or internet), I wondered if they would even have nori or wasabi. The only other sushi bar I've known in Havana is Sakura, opened with backing from the Japanese embassy. Every time I went, it was closed, or half the things on the menu were unavailable.

Now, though, Havana is in the throes of a food revolution. Since Raul Castro succeeded Fidel in 2008, reform has gathered pace. He has lifted bans on mobile phones and computers, allowed Cubans to travel without exit visas, sanctioned the buying and selling of houses, and deregulated the small-business sector.

Business owners, farmers and construction workers can borrow from state banks, and rules governing private restaurant ownership have been loosened. The number of covers allowed has grown from 12 to between 50 and 100 with special permission. Instead of paying 1000 Cuban pesos ($975) for a one-off opening fee (50 times an average monthly state income), venue owners pay a monthly fee of 150 CUPs.

Cafes, paladares, bars and ice-cream parlours have sprung up overnight. Some crashed and burnt, testament to the lack of entrepreneurship in recent years. Others are marvels in the making.

Before these changes, there was no inspiring food story to tell in Cuba. Cuba's gastronomy, a rich fusion of Spain, Africa and Native American, was sacrificed on the altar of survival. The US embargo, and the collapse of the Soviet Union and its financial backing, had dealt the state a near-fatal blow. During the Special Period from 1990 on, Cubans lived on rice and beans. When paladares - private restaurants - were legalised, falteringly, from the 1990s onwards, a handful of sophisticated affairs flourished, such as the film set-beautiful La Guarida, but most were uninspired front-room projects serving stodgy comida criolla: roast chicken, pork or fish served with rice, beans, and salad. Street food was pizza with the consistency of cardboard, gag-worthy cheese sandwiches, and chicken fried in cheap oil reused for the hundredth time.

In the hotels, the horror of the buffets has been documented on TripAdvisor: smoked salmon balls that taste of cat sick; Spam-like meat slapped on your breakfast plate. I've long known that casas particulares (bed and breakfasts) are the only dead-cert for a decent breakfast: heaped plates of tropical fruits, fresh rolls, peasant cheese, and three-egg omelets.Those days are, if not gone, numbered. At the lower end of the market, funky hole-in-the-wall places are popping up. At Waoo snack bar (Calle L y Esquina 25; Vedado; +53 7 832 8424) near the state television building, I order a salad of serrano and quail's egg with a funky chocolate-balsamic dressing. Octopus, bruschetta, tabbouleh and arancini grace the menu - unremarkable for Melbourne or Sydney, rare food indeed for Havana. At Nao snack bar off Plaza de Armas (Calle Obispo 1 entre San Pedro y Baratillo, Habana Vieja; +53 7 867 3463; naobarpaladar.com), I try tasty empanadas, aromatic fried malanga, and tamales (corn) with pork. I queue with locals at a corner shack on 5 y A doling out pork burgers teamed with pineapple, egg, and jam and soft cheese - tastier than it sounds. In Old Havana I discover El Chancullero (Calle Teniente Rey 457, +53 7 872 8227) , a Spanish-style drinking den with handwritten tapas menus (vast prawn enchiladas and chicken kebabs for $3 each), graffiti on the walls, gilded youth, and European-pitched music that shirks the blaring Latin trend.

At the top end, chefs are defecting from the classier state restaurants and returned expats are fulfilling long-held dreams as creative dishes from around the world fuse with Creole recipes to create a new, upscale Cuban cuisine. Michel Miglis' Casa Miglis (Lealtad 120 entre Animas y Lagunas, Centro Habana; +53 7 8641 486; casamiglis.com) is the first restaurant to open serving Scandinavian cuisine (yes, really) since the revolution. The menu features such rare ingredients as "lingon berries from deep in the Swedish forests". The light and airy interiors are designed by Swede Andreas Hegert. Staples such as Skagen toast and meatballs join spicy couscous. Aside from the corny 1980s ballads, I could be in Madrid or Lisbon.

What owner Michel is excited about is the "strong will on the part of the Cuban government to help the private restaurant sector to succeed. There is for the first time a real, positive communication". Anywhere in Europe, Miglis' restaurant would be par for the course. In the decrepit streets of Central Havana, it feels like a little miracle.

His is one of many. At Starbien (Calle 29, #205 entre B y C; +53 7 830 0711), an immaculately renovated mansion in Vedado, I sit on the balcony and eat carpaccio and chicken sesame shaslik, looking down on a garden full of newly wealthy Cubans. At Rio Mar (3rd y Final, 11, La Puntilla, Miramar; +53 7 209 4838), I gaze across the water and eat pecorino and perfectly roasted vegetables; at Ivan chefs Justo (Aguacate 9, esquina Chacon, Central Havana; +53 7 863 9697), shiitake mushroom risotto; at La Carboncita (3ra 3804 entre 38 y 40, Playa; +53 7 290 4984) Italian chef Walter Ginebri's new paladar, every possible type of fresh pasta, sauce, and thin-crust pizza imaginable.

At other times, the realities of Cuba get in the way. At El Cocinero (Calle 26 entre 11 y 13, Vedado; no phone as yet), a restaurant-bar on the cusp of opening, I am welcomed by a Miami-trained cordon bleu chef who wants to cook me a sample dish but his plan is spoilt by a power cut. (His alfresco rooftop is as industrial and chic as any urban bar in London's Shoreditch or on Manhattan's Lower East Side. "There will be no reggaeton music," he tells me solemnly.) I try to visit Castas Y Tal (Calle E 158-B, entre 9a y Calzada, Vedado; +53 7 833 1425), a paladar in a Vedado high-rise, but arrive during another blackout. Waiting on the steps for the lights to resume (they don't), I discover I am sitting next to the chef, Ransys. Feted for being a woman in a macho world, she tells me she relies heavily on friends outside Cuba to bring spices. "Without them, my lamb marsala would be nothing," she says.

Esencia Experiences, a company offering tailor-made travel at Cuba's top end, offers a tour of the paladar scene and a crash course in Havana's complicated food story. Its secret weapon is Tanja Buwalda, a warm Irish Cubaphile and self-confessed food nerd who has her own Cuban-food blog.

Buwalda, who ran her own Asian fusion restaurant in Cork, says she has learnt a lot about cooking in a Cuban way - slowly. "I have learnt to use a pressure cooker, to soak beans a day before, then, the day after, to use those same beans to make a soup or a casserole. I have learnt to sit my meat in marinade for a long time, and to wait patiently for my fruit to ripen. I never throw anything out. I go to the market daily and buy for that day, or recycle leftovers. Cooking here is a metaphor for life. My life, like my cooking, has slowed right down."

The experiences Buwalda offers are not-in-the-guidebook stuff: a day trip into the countryside on a Harley to a small farm, including lunch with the farmer, and an exploration of Havana through its street food. (From the barrio to the embassy district, she knows the best churros - deep-fried doughnuts; the best Cuban biscuits; and the best pan con lechon - slow-cooked shredded pork in aromatic vinaigrette on a soft white bun.) She can introduce you to the nascent world of vegetarian Cuba, taking you on an early-morning talk and tour around the Nunez-Jimenez Foundation museum, founder of permaculture in Cuba or, on a home-cooking day, a tour of the markets then back to the home of a Cuban to prepare and share a meal. We visit two organoponicos - Havana's urban vegetable gardens. After the fall of the USSR in 1990, vacant state land turned into "people's plots": necessity being the mother of invention. These days, permaculture devotees travel from all over the world to check out these high-yield projects, part of Cuba's urban wallpaper.

Tanja also takes me to a range of mercados. "We'll get there before 11am, otherwise it's too hot and everything good has gone," she says. Our first stop is the state Tulipan market, where there is plenty of produce: basketball-size papayas, vast yucca, oranges, tomatoes, green peppers, every kind of dried bean, garlic, green beans, lettuces and horseradish.

"No fruit or vegetables are imported here," Buwalda tells me, "so when you take a tomato home and bite into it, you are tasting Cuba - heat; red, rich copper soil; hand-grown food with little machinery - all of that is captured. I've tasted eight types of mango here."

We set off to the private 19 y B market, which they call "El Mercado de los Millonarios" - it's pricey and frequented by expats and owners of bed and breakfasts and paladares. "Doctors and teachers don't shop here," Buwalda says. Here you can find exotic fare for Cuba: green chillies, ginger, ready-made salads, quail eggs, cauliflower and broccoli (little encountered, unbelievably), beetroot and fresh herbs. At EJT Market on 19 y K, stocked with products cultivated by youth before military service, I learn about food sourcing. You buy pork in the state market, chicken from state shops retailing in the convertible peso, and fish and seafood on the black market, though most regular Habaneros cannot afford it (the state sends its fish for export or to the tourist hotels and restaurants). Paladar owners work a complex network of black-market contacts for cheese, butter, yoghurts, seafood and bread. Food by Australian standards is cheap, with fruit and vegetables and some meat costing, on average, $40 a month. However, the typical Cuban gets paid the equivalent of $25 monthly, so most have a second or third job, or are subsidised by family abroad.

Restaurant owners face astonishing challenges in supplies. Because of the embargo, Cubans cannot buy food on the open international market. Production is low because of a collectively farmed, under-invested agricultural sector. Corruption in the supply chain is rife - the head of onion production in Sancti Spiritus province was jailed last year for having the lowest onion harvest in history despite millions of pesos of investment.

The orange harvest rotted for lack of pickers, and Pinar del Rio's yucca harvest suffered from a shortage of trucks to distribute it. Eggs break on long journeys for lack of proper packaging. Once you know all this, you realise it's a miracle paladar owners manage to pull it off at all.

I chat to Hector Higuera, maitre d' of Le Chansonnier (Calle J 257 entre 15 y Linea, Vedado, +53 7 837 1576), Havana's hottest paladar. Higuera gutted a classic colonial home to create an industrial-chic bar and a restaurant with a reclaimed-metal feature wall.

Like Michel and Ransys, he relies on foreign friends to stuff their suitcases with the spices, mustards, chocolate, tahini, foie gras and parmigiano that keep his business going.

"I don't even have a credit card to shop over the internet," he says. His fish come from the fishermen, some vegetables from an expat Japanese female farmer, his pork direct from the countryside, and his fresh pasta from an Italian expat. There are no contracts with suppliers, so it's "organised chaos". There is no provenance ethos in Cuba, Higuera says. It's local and seasonal because there is nothing else. Most of his clientele comprises visiting foreigners, Havana-based expats and wealthier Cubans, but in the bar he sells beers for 1.50 CUPs: "Otherwise I would never see my friends."

All this talk of food is making me hungry. So we tuck into babaganoush, curried shrimp and pan-fried cheese with onion confit. This fashion for foreign influence is unsurprising in a country so long in enforced isolation. I welcome it with open arms, partly because it gives me the variety I crave in order to continue appreciating the simplicity of comida criolla.

Some things you have to keep Cuban, though - such as that earthy full stop at the end of the meal, the cafecito.

I am relishing one alone on Hector's elegant terrace. Fierce and smoky, softened by a honeyed aroma, it packs a punch and is just like Cuba itself: a bit in your face, a bit much, dark, intense - and sweet as hell.

FAST FACTS

Getting there Due to the US embargo on Cuba, you cannot have Cuba on your ticket if you transit through and/or use any US airline. You have to buy two separate tickets. United Airlines has a fare to Mexico for about $2490 return from Sydney and Melbourne including taxes. From Sydney, fly to Los Angeles (13hr 25min) and then to Mexico City (3hr 34min). see united.com. Aerovias de Mexico has return fares to Havana (2hr 35min) for about $515, including taxes; see aeromexico.com. It is also possible to fly via South America but times are longer.

Touring there Cuba travel experts Esencia Experiences specialise in tours from Santeria to surfing and salsa.

Staying there The Hotel Saratoga has rooms from $231. Phone +53 7 868 1000, see www.hotel-saratoga.com.