Tijuana. You know the place, bro. TJ, dude! That crazy-ass Mexican party town, a hop across the border from sunny SD. Legal Vicodin, man, over the counter. All that shit to make your dick hard, too. Because in the cheap titty bars, they go as far as you want. Oh man. Cheap brewskis, too — no shit with carding. It's Mexico, mofo, they don't have laws there. They love us there, bro. We rule. Oh dude, you're going to fucking dig TJ. Once you're spent, you just get the hell out man, back to civilisation. Over that border, the one that keeps them out dude. God bless America, man. Go State!

this image is not availablepinterest
Bear Grylls//Digital Spy

OK, perhaps I've gone a little too far. And got it all wrong. Perhaps the visiting hordes, who've been pouring over the border since Prohibition days — topers, gamblers, soldiers, sailors, stoners and sybarites alike — saw beyond the sex shows and cut-price Corona, the legal highs and lurid lows. And TJ's eternal reputation as a full-strength Mexican fantasyland, the dirty mistress, the ay caramba! courtesan, a place of guilt-free excess and sin without consequence. The start of The American Dream, the border city where anything is possible (for a price). Or is it the end?

Perhaps instead they viewed Tijuana as the gateway to Mexico, one of the most magnificent, beautiful, big-hearted and thrilling countries on earth. Then again, maybe not. Tijuana will never win any prizes for pulchritude. The city sprawls and meanders, stutters and stumbles, drones on, loses the thread, then starts afresh. Up hills and down valleys, sun bleached, blitzed and washed out, lurking under a grim pall of nicotine-stained haze. Flying in from Mexico City, over ragged mountains, all you see is beige. Desert. Scrub. Sand. An entire city draped in yellowing rags.

It doesn't have the epic, frantic grandeur of Mexico City, the colonial splendour of Guadalajara, or the faded, sun-kissed glamour of Acapulco. Or the taut skin, tit job and gleaming teeth of gym-trim San Diego, 20 miles to the north: the US city hidden behind that fierce, forbidding border with the never-ending gleam of vicious razor wire and dull, mean, interminable, corrugated iron fence, arc lamps, unblinking cameras and eternal tales of woe. You could hurl a ball from Tijuana airport, across the narrow sliver of no-man's land, and have it plop into San Diego County, USA. Or simply skip from Arrivals, over the new walkway, and into the Land of the Free. Providing you have the right papers, the good old Green Card, that magic Drink Me potion that shrinks you down to fit through that all-too tiny door. No, border towns rarely compete, at least when it comes to looks. But Tijuana has charm, and soul, and cojones. Big, swinging cojones.

this image is not availablepinterest
Bear Grylls//Digital Spy

The city is no longer awash in America's excess. Thank God. The famed Avenida Revolución, once slick with piss, puke and quick-spent passion, is now about as raucous as Cadogan Square on a Sunday night. Sure, the "American pharmacies" still flog over-the-counter salvation. And if you look hard enough, you'll still find the strip clubs and sex shops, hidden away on the back streets.

"But it's changed a hell of a lot from 10 years back," says Bianca Castrocerio, Tijuana resident and pastry chef extraordinaire. "It's a lot more trendy now. Chefs come from all over the country to eat, and get inspiration. The state of Baja California is becoming a true food destination." From gutter town to gleaming gourmet mecca: things are certainly looking up.

The Baja California Peninsula, shaped like a bony finger pointing down the north west side of Mexico, is a land apart. With the Sea of Cortez to the east, and the Pacific crashing to the west, it's the northernmost and westernmost of Mexico's 32 federal entities. It only became a state in 1952, and is still sparsely populated, with most of its inhabitants living in the capital, Mexicali, or Ensenada or Tijuana.

You'll find chapter and verse on the glorious gastronomy of Oaxaca, Jalisco or Yucatan, but Baja California barely warrants a mention. I trawl though my favourite Mexican food writers, from Patricia Quintana and Susanna Palazuelos to Elizabeth Lambert Ortiz, Margarita Carrillo Arronte, Rick Bayless and Diana Kennedy. And save the odd fish taco, there's nothing. All, though, is about to change.

"It's a cauldron here," says Ruffo Ibarra, the boyish chef proprietor of Oryx Capital, one of the new wave of restaurants drawing the hip and hungry to Tijuana. "Everything's blended." The traffic moves at a steady pace, the air scented with masa (corn dough) and diesel, miles removed from the angry gridlock of Mexico City. At traffic lights, the usual children weave through the stationary cars, flogging chewing gum, newspapers, crap Chinese toys and sweets. "Everyone seems to end up here, from all over Central and South America. Because everyone wants to go to the States but not all get in. So they get stuck. Stuck here."

"Everyone wants to go to the States but not all get in. So they get stuck. Stuck here"

Castrocerio, Ibarra and I pull up to the Mercado Hidalgo, dozens of semi-permanent stalls huddled around a sun-bashed square. We pass piles of dried chillies, mounds of pastes for mole and adobo, barrels of dried shrimp, bundles of sage, paddles of nopal cactus, great garish ears of corn in every hue and tart tomatillos, a startling green.

"Baja California is as American as it is Mexican," says Castrocerio as we walk to Tacos Fitos, a tiny two-man beef birria cart. "When I was young, everything was shipped in from the US. It's closer than the rest of Mexico." The men on the stall chop beef and tripe with speed, dipping tortillas into bright orange fat, and throwing them on the hotplate, so they puff and swell. In one deft move, they flip the meat on to the taco, sprinkle with onion and coriander, and pass it over on a plastic plate. A squeeze of lime, a whack of fierce Chile de árbol salsa, then handheld heaven. The glorious fat dribbles down my fingers, through my hands, onto my shirt. There's depth, heft, heat and grease and joy — the very essence of taco delight. Washed down with a plastic cup of consommé, richly bovine, dotted with globules of glee, fatty and fantastic. I wear my stains like medals.

No time for faffing. "There are lots of refugees from Haiti," says Ibarra, as we get back in the car, chilli still stinging my lips. "Obama said he'd let them all in, so they arrived. But it got complicated: 300 a day came, but only 15 to 20 were let in. There are 10,000 now. Educated people, engineers, architects, stuck here, without papers." He shakes his head. "Still, it's exciting to see how the culture changes, how the food changes. A lot of different cultures in a small place, all trying to get through that tiny magic door. That's got to be good for Tijuana."

Oryx Capital, with its exposed bricks, leather banquettes and speakeasy bar, could be in Shoreditch. "This is Cali-Baha food," says Ibarra, donning his chef's whites. "I got bored of cooking fine dining, so [now] do comfort food." Damn, it's good. Spanking fresh raw yellowtail with mescal and coriander flower, a taco, stained black with squid ink, containing crisp, battered fish and guacamole, pickled onion and a whack of habanero. Our first taste of the famous Baja fish taco is modern but majestic.

this image is not availablepinterest
Bear Grylls//Digital Spy

It's a pioneer like La Querencia, one of Tijuana's most famous restaurants and our next stop. This place is said to have started the Baja revolution. The walls are plastered with photos of chef Miguel Angel Guerrero battling bluefish, shooting doves and stalking deer. Stuffed bears and pheasants and antlers dot the room. Guerrero is hard, handsome and hirsute, the sort of man who could wrestle grizzlies while whittling wooden toys for his kids.

"Baja California was never conquered by the Spanish," he growls as we eat yellowtail, caught by the chef yesterday, with venison crackling. "So was never subservient to anyone. There's a freedom, an openness, whether in food, wine or art. There are no rules here."

Wild venison tartare with chervil and fried capers is mighty yet refined, beautifully balanced, with a swathe of cool smoked oyster cream. "In Baja, we have everything," says Guerrero. "An ocean, a sea, and everyone has their own garden… 25 years ago, we had no identity. Now things are different."

It's our fourth meal, and greed turns to satisfaction to satiation to stuffed. Such is life. The endless edible struggle. We soldier on.

"There are so many different people coming in all the time, from all over the world," Castrocerio says, "so we're always evolving. "

this image is not availablepinterest
Bear Grylls//Digital Spy

Guerrero nods. "In Puebla, everyone is guarded with their family recipes," he adds. "Here, everyone shares. Right now in Baja, we have the chance to create our own cuisine." He grins. "In Baja, we cook differently, because we are so far away. Of course, we have birria [a spice stew] and carnitas [slow-cooked pork] and all the rest. But we have French and Italian influences, plus our Chinese and Japanese foods are amazing. And three world-famous dishes come from here. The margarita, the fish taco and caesar salad."

Ah, caesar salad. The Cardini family is still at war over whether it was Caesar or Alex or Livio, Italian immigrants from Lake Maggiore, who created the damned thing. Whatever the truth, a salad was invented using lettuce, raw egg, garlic, croutons, anchovies, mustard and Worcestershire sauce. Caesars, a tourist trap on Avenida Revolución, is where it all began. Allegedly. It's not without charm. The floors are chequered marble, the roof panelled wood, and there are murals and margaritas. And the salad, mixed table-side with much po-faced ceremony, tastes like, well, caesar salad. Seasoned with history, tossed with legend. Striptease music plays on the speakers. "A salad undressing," jokes Bill Knott, friend, fellow food writer and seasoned trencherman. We pay and move on, out of Tijuana, down south.

Soon, we leave the border behind, instead staring at the Pacific Ocean and the sun melting into the distance, passing beach resorts and American-owned condos festooned with satellite dishes. A huge statue of Jesus gazes down, his hands held out in welcome.

The sun is losing its power as we pull into Puerto Nuevo, a tourist town built on lobster. It's quiet now, out of season, but at La Casa de la Langosta, we just about manage a whole beast, grilled, then ripped from its shell, doused in butter and folded into a huge flour tortilla, thin, elastic and translucent. With beans, good beans, and about the 10th michelada (beer with lime juice and salt) of the day.

this image is not availablepinterest
Bear Grylls//Digital Spy

The sun's gone now, along with any vestiges of appetite. Nothing more can pass my lips. Save a glass of red wine at Adobe Guadalupe, a hacienda-hotel and vineyard in the Guadalupe valley. It's a revelation, my first taste of good Mexican red wine. I fall into heavy slumber, dreaming of lettuce, naked and unadorned.

I wake, to brilliant sun, and acres of vineyard, and beautiful horses, grazing in the distance. The landscape could be Sicily in summer, all gnarled olive trees, umber hills and a familiar Mediterranean feel. Breakfast is in Ensenada, a port town 20 minutes south.

We pass through the valley and hit the Pacific once more, breaking to our right. Fishing boats sport rods like porcupine quills and putter in and out. Ensenada is a working port with vast containers and hulking cranes bent double like arthritic old men. But we've only one thing on our minds: La Guerrerense tostada stand, owned by Sabina Bandera, small of stature, big of legend. I've met her before, eating her epic tostadas in Mexico City and Acapulco. But this is a place of pilgrimage. One stall, serving up a crisp seafood tostada that could make that bishop forget his hot blonde and still kick a hole in that stained-glass window. The low, filthy growl of sea urchin, chunks of freshly shucked pismo clam, peanut and chipotle salsa, slices of avocado. Three bites, of zinging, primal, oceanic vim — Neptune's roar meets mermaid's sigh. We chew in silence, grins slathered like salsa across our faces. Damn, it's good to be alive.

A swig of mescal, or two, at Sabina, our hostess's new eponymous restaurant over the road. More fried fish tacos with crisp white cabbage, and seafood posole, and cold smoked tuna tostada, and sea snails in hot sauce, and octopus tentacle, soft and charred, wrapped in tortilla, slathered with guacamole. The best seafood, allowed to sing shanties to its own brilliance. If I lived in Ensenada, I'd move in.

this image is not availablepinterest
Bear Grylls//Digital Spy

But wine calls and off we slog, back up to that "fog moistened valley", the home of Mexico's oldest vineyards, where Spanish friars started making altar wine in the 18th century. "The Guadalupe valley is a small vacuum of international wine makers," says Tomas, a Swiss fellow, at Casa de Piedra. "Like Napa in the Seventies." I find wine tours dull. Skip the chat, let's drink. "Ten years ago," he says, "there were no tours. And very little food. A one-lane highway. But gastronomy and oenology grew hand in hand. And you need a paved road to get the Americans here."

We drive a few more minutes, along that paved road, to what looks like a post-apocalyptic Mad Max camp. Roofs are made of upturned boat hulls, walls constructed from different coloured boards, and there's a small, incongruous lake in the middle. We're greeted by a man with flowing white hair and a strong Derby accent. The great winemaker Phil Gregory. He takes us through some of his friends' favourite reds. Bodegas Henri Lurton, made by the French: rich, deep, spectacular. Las Nubes: complex, smooth. And his own Vena Cava. I'm blown away. Even Bill, a serious oenophile, nods his approval. "Very good," he murmurs.

"We arrived a little less than 15 years back," says Phil over more octopus tacos. "Hugo D'Acosta was the man who started it all. A Bordeaux-trained Mexican. Persuaded people to use better grapes and processes. His work has changed the face of winemaking and growing. Fifteen years ago, there were 19 wineries. Now there's 152." He laughs. "We're the Wild West, so appeal to real pioneers. The quality of the grapes, the terroir, and the lack of rules… I started with a barrel-and-a-half. We grew slowly. We make wine from the heart."

We wander over, abuzz with half-cut excitement, to La Villa del Valle, Gregory and his wife Eileen's home, and also an exquisite hotel. Bags are dropped before a hike through a wild vegetable garden, fecund with coriander, chard, scarlet tomatoes and tiny potatoes, towards lunch. Our second of the day, at Corazón de Tierra, just past the garden.

"The wine, the house, the garden… it comes from what we love," says Eileen. The restaurant sits in a temporary structure, like a modernist hippy retreat with wide glass windows and chairs backed with Mexican embroidery. The food is assured, elegant, blessed with flavour and the lightest of touches. Pert oyster with hazelnut butter and sage, an astonishing mole blanco, wild partridge with artichoke purée. No pretences or pomp, just exceptional ingredients. Chef Diego Hernández Baquedano sure can cook. We drink Phil's Big Blend red and unfiltered Chardonnay, and chatter turns to where we're going to feast next.

Which turns out to be Deckman's, lunch number three — and perhaps the finest of them all. It's a 10-minute drive across the valley to where Michelin-starred Drew Deckman, burly but graceful, mans the grills. The floor is covered with straw, the tables and chairs utilitarian, the rough adobe walls open to a view of pure bucolic delight. Slow jazz mixes with the chatter of roosting birds, the smell of wood smoke and searing fat.

We eat more oysters with shallot vinegar, and thick slices of raw tuna, seasoned with tiny piles of salsa and onion. The flavours are big but the presentation precise and pretty, with edible flowers and zinging salsas. And steak to make a carnivore cry, the crust thick, burnished and salty, the meat deep pink and tasting of a life well lived. Under the guise of rustic simplicity comes pure undiluted genius.

"It's the place where the dissatisfied come to find satisfaction," says Bill. We're drunk now and, the sun long gone, the inky night is lit by tiny orange bulbs, the air alive with the crickets' song. We booze on, comforted by the glow of coals, perfection found in the middle of this most magical of states.

this image is not availablepinterest
Bear Grylls//Digital Spy

But there's more. Much more. We fly down to Cabo San Lucas, in Baja Sur, where the models and movie stars hang out. We're deep in the desert here, at the tip of the peninsula. Palms sway, the waves break on handsome beaches, and everywhere you look, building is underway — cranes, trucks and workers, never ceasing. San José del Cabo is small and colonial, but blessed with a sort of expensively barefoot Cali-Mexican allure. Juices, detoxes, art galleries and yoga classes. There's Drift San José, lots of concrete and artisan mescal. And La Lupita, a taqueria where the tacos al pastor is up there with Mexico City's.

Life moves slowly here. Even the breeze is languid and laid-back. The saline air is fresh as the sky, the landscape wild, unmanicured, sunnily sexy. The Cape hotel is worthy of mention. It sits over a surfer's beach. The balcony of my room has a hammock, so I spend hours swinging, lolling, swigging down the view of the famous rocky arch and endless ocean. Proper tacos, icy micheladas, games of pool and the unfettered joy of a climate without compare.

Lunch at Claro Fish Jr, a fish taco mecca, where we eat marlin tacos and prawn aguachile under a palm-thatched roof. Then dinner at Manta, back at the hotel, gazing out over that mesmerising sea. It's black now but the breeze still blows, the walls open to the elements. Manta's the new place from that greatest of Mexican chefs, Enrique Olvera. He's warmly ursine, with soft eyes and soft voice. We sit talking at the bar before dinner.

"There's an incredible magic here," he says. "The desert gives it a tranquillity that is hard to find in the rest of Mexico." This is one of the most famous chefs on Earth, with restaurants in New York and LA. Yet here, he is at peace. "I'm at my most relaxed in Baja Sud. It gets into your soul." By now, we feel the same — like palms (albeit over-fed, mescal-breathed palms), swaying softly in the breeze.

Chocolate clam aguachile, beef tacos with shiso, more charred octopus: modern, clean, utterly confident, not a bite out of place — food you'd eat again and again. We can hardly wrench ourselves from the hotel, but manage, eventually, to visit the town of Todos Santos, one hour north. We drive past the fridge repair shops and pool cleaners, the engine rooms of the tourist trade. Trucks roar past filled with federal police, their faces shielded with balaclavas, their automatic rifles erect, a reminder that even Baja is affected by those infernal narco wars. Not sanitised but safe.

this image is not availablepinterest
Bear Grylls//Digital Spy

Todos Santos is small, tidy, colonial and sleepy. We pass altar boys, in red and white, ready for mass in the pretty church. Drink a michelada in the Hotel California, where a guitarist croons that bloody song at least 50 times a day… "such a lovely place". Lunch at Javier Placenta's Jazamango, in another wonderful garden hewn from desert rock. So much to inspire and delight with more grills and kitchens open to the elements. "The people in Baja Sur are not rich, but neither are they hungry," we're told by our friend Manuel Diaz. Nor are we. Another flawless lunch, of sprightly aguachiles, fresh herbs, crisp suckling pig, lamb tacos and clams with Thai curry paste.

"We are so tired of the stereotypes, about Mexico and Baja," says Diaz, "this is the new generation." By now, I've fallen for Baja California hard. A land apart but Mexican to its core. Tijuana: dully dusty but delectable. Ensenada: with that bracing saline allure. The valley of Guadalupe: for its wondrous wine and restaurants. And Baja Sur. Paradise, at the tip of the finger. The long afternoon stretches languorously into dusk. We should go. At some point. But what's the rush? Down here, time waits for all men. We order another bottle, sit back and thank God, once more, for Baja.

Tom flew to Mexico City on Aeromexico on board its Boeing 787 Dreamliner, with a premier seat that reclined 180 degrees into a full flat bed. Aeromexico also offers Clase Premier customers complimentary transfers to and from London Heathrow T4.

To book visit Aeromexico.com