How to eat paleo (ish) while travelling

Southern Europe so far: je marche, Je mange. That’s pretty much been the picture for the past five weeks. I don’t really do museums or galleries. I travel to eat. I hike to eat. I eat to hike.

6be0c2cec56511e18e3c22000a1e8b97 7 How to eat paleo (ish) while travelling
At Mercado de San Miguel in Madrid: oysters and alborino

If you’ve been following me on Instagram and Twitter you might have noticed that I’ve been eating a lot. Like, more than ever. And I’ve done so on a paleo(ish), gluten-free, sugar-free regime with a healthful, robust, full-fat, fully passionate focus.

How, so many of you keep asking me? How am I staying healthy? How am I staying starch-free in the UK, Southern Spain, Provence, and now Greece when pretty much everything comes on top of, surrounded by and engorged with potatoes and bread? Or a croissant?

Well, how about I tell you in pictures.

(PS: If you want to follow the rest of my World Wanders, follow things on Instagram and check out #worldwanders. I’m posting some of the pics on Twitter and Facebook too).

First up:

  • Being starch-free while travelling is a little bit of a challenge. Bread is everywhere in Europe and it’s good stuff. The best. So are the pastries. The locals all eat the stuff. Ditto potatoes and pulses.
  • But, surprise, surprise, in Spain, in particular, everyone seems to be getting sick from the bread, at least. Celiac’s disease is rampant. So much so “sin gluten” (In Spanish, “without gluten”) is understood everywhere. The tiniest deli in the smallest town will have a “sin gluten” section of breads and biscuits.Why so? I think it’s because the Spanish have been eating too much bread for too long. Every. Single. Meal. Comes with bread, is placed on bread, is mixed with bread. It’s a tradition that stems from a history of being poor…and bread is poor man’s food. Good for fattening fast. (The situation in France, I think, is a little different and possibly the quality of their flour is different – higher quality, less gluten. In Greece, well, I’ve just arrived. But I’ll try find out.)
  • I’m not a militant paleo adherent. I don’t eat bread, I avoid grains and potato and I minimise sugar. All for particular health reasons. But I’m not a fanatic (leaving aside gluten).
  • If you’re traveling you might want to consider eating paleo anyway. First, when you cut the starch it makes room for the more densely nutritious food, which you need while moving about and is far more often the stuff you really want to experience. Second,

 My Theory on Weight Gain While Traveling: it’s the bread.

When we travel we eat a lot more of the stuff because it’s cheap and is force-fed to us at restaurants. This, along with a lot of weight bearing exercise – carrying packs etc. sees us pack on the bulk like an old milk maiden. Also, if you tend to get a little bloated, grains and pulses are not your friends while en transit.

  • BUT, bread aside, Europe is fanatically embracing of the value of good protein and fat. Good meat is revered. Cheese is a meal. Everyone is comfortable with oil and fat. I’ve found it all very easy to eat here, and to eat extraordinarily well.

So, some little paleo tricks for the road:


I mixed up some linseeds, nuts, chia seeds and coconut shreds in a bag before I left. I’ve been eating this in yoghurt. Buy Greek yoghurt, organic. It’s full fat (skim is full of sugar). Nerdy, but, hey, that’s me.

On my big hiking days (I’ve done ten days of hiking so far, for 4-7 hours each day), I eat scrambled eggs and jamon (a typical ham dish in Spain; in France much the same).  Sometimes with asparagus. Often two serves. Or three. Or I’d have a plate of jamon and cheese.  Or four. Waiters in small towns laughed at me. I do the same in hotels. At the continental buffets I eat yoghurt, ham and cheese.

8b8150acc81811e1a8761231381b4856 7 How to eat paleo (ish) while travelling
A pretty breakfast of stuff from Provence at Les Rosees Hotel in Mougins

Meat and fat is never the problem. Veggies might be, especially in Spain. I’ve been dedicating a meal to just eating a bunch of whatever I can find. I tend to do it for breakfast or lunch, picking up stuff from a market. I buy nuts and sunflower seeds (these are sold like chips in Spain for 30c), cucumbers, beans, a peach, a tomato, witlof. I’ll plan this. I stock up the night before if I have to. Hunt down a small market.

5ae1624ac5af11e181bd12313817987b 7 How to eat paleo (ish) while travelling
How tomatoes should look!
639b9878c13211e19e4a12313813ffc0 7 How to eat paleo (ish) while travelling
After a three-hour hike I came across these (Sierra Nevada)

My favourite thing has been to catch a train early, with a little picnic of things and a coffee (I’ve been drinking coffee over here, quite happily, a few a week). Very little makes me happier.

4aa6afb0c76311e19894123138140d8c 7 How to eat paleo (ish) while travelling
Stocked up: at the Arab markets in Marseille...on my way to Cannes
5ccf62f6bbbd11e1abb01231382049c1 7 How to eat paleo (ish) while travelling
On the train through El Churro on the way to Ronda in Andalucia

A tip: when desperate for breakfast/lunch at a Spanish railway station etc ask for one of their super CHEAP rolls (about 2 Euro) without bread. You’ll get a stash of ham and cheese. It’s generally really good quality, too.


On hiking days I don’t really eat lunch. I don’t want to carry it. Hence the egg, cheese, jamon overload I mentioned above. Sometimes I take a cucumber.

34c728c4bd7611e180c9123138016265 7 How to eat paleo (ish) while travelling
I'd walked five hours when I took this photo...between Zahara and Grazalema

But on “explore the town” days, well, lunch has been my entire raison d’etre for the day. I map out my destination and wander a route that gets me to lunch at about 2pm. Once there, I try the cleanest, most local protein. Eat what they do best….it will be local, freshly caught and they’ll take pride in the cooking and preparing.

In London, I rode two hours across town and spent three hours at The Borough Markets eating my way around the joint. I think it’s one of the best markets I’ve been to. Here I gave duck a crack. And Welsh cheeses. And the most amazing hot chocolate.

5291bb24b22e11e1abd612313810100a 7 How to eat paleo (ish) while travelling
The Borough Markets
51dbf078b22e11e1be6a12313820455d 7 How to eat paleo (ish) while travelling
Cacao nib and chilli tea - blew my head off! At Rabot Estate at Borough Markets

Another day, I crossed town to eat at The Albion. I look up the website the night before, do my research (I also poured over a bunch of “slow food” guides in a bookshop for some great insights. Slow food directories – online as well – are a great way to find paleo-orientated eateries, as they profile places that showcase their local wares…which are often meat, cheese, vegetables).

99ea7610b2fa11e1989612313815112c 7 How to eat paleo (ish) while travelling
Pork crackling!!!

In Bristol my brother and I drove an hour to eat at The Ethicurean where they grow many of their own veggies in a massive garden out front:

d201e86cb84a11e1a9f71231382044a1 7 How to eat paleo (ish) while travelling
The Ethicurean: ham hock broth with a poachie...all local produce

Back in London, pubs – especially good pubs – are a boon for high quality meat, and often cuts and meats that are very ethical and environmental (ie: pasture-fed and nose-to-tail etc).

829129d6b49f11e19dc71231380fe523 7 How to eat paleo (ish) while travelling
Berkshire wild roe deer with hispi cabbage at The Harwood Arms
584f1456ba2811e1b10e123138105d6b 7 How to eat paleo (ish) while travelling
In Malaga, I walked 6km to eat their famous sardines cooked in a boat. And then back again. That day I also bought some beans from a market, to balance things out.
937c83e8be9611e1a9f71231382044a1 7 How to eat paleo (ish) while travelling
7aada098bd7611e18cf91231380fd29b 7 How to eat paleo (ish) while travelling
In Zahara, at Al Lago, these sardines were astonishing. And the calamari...
6240490cc56411e1aaec22000a1e88af 7 How to eat paleo (ish) while travelling
In Madrid, I ate at their “markets”: not so much produce markets, but places to buy little dishes and a glass of wine and then stand and chat.
d36207e2c56411e19ab222000a1e8819 7 How to eat paleo (ish) while travelling
You buy small protein things on sticks for a few euros

This place below has a restaurant on top where they’ll cook the seafood or meat you’ve just bought. Man! Clever! They serve it with vegetables (1 Euro).

7195de3ec5d311e19ab222000a1e8819 7 How to eat paleo (ish) while travelling
Mercado de San Anton in Madrid


Again, dinner as a destination is my main game (if I pass a museum along the way, fine).

Southern Spain is all about buying a drink and getting tapas for free. Which is rather….bready. And I can only drink one boozy drink. So I’d go for a little tapas first (with a glass of Tio Pepe – I love the dry saltiness, especially after a long walk….and usually it costs about 1 Euro) and then head somewhere else for a proper dinner that I pay for after.

33f83480bf1311e1af7612313813f8e8 7 How to eat paleo (ish) while travelling
A "Rueda" drunk in Ronda...I'd just hiked over those mountains that afternoon

And, of course, there’s always cheese. I came to Europe for the cheese. It’s a way of life, it’s the smell of the countryside, it’s art, it’s everything life should be about. I eat it without bread of course. Cut to the chase. Banons, thoms, St Nectaires…this stuff makes me happy!

b2c0d122ca1311e1bef722000a1e8bb5 7 How to eat paleo (ish) while travelling
At Columbe d'Or in St Paul de Vence, Provence

Some other things at dinner time:

  • Ask for no potatoes.  Chips or fried potatoes come with everything in much of Europe. Ask to replace them with something resembling a vegetable. Generally they’ll think you’re mad (because veggies are considered peasant food, traditionally, particularly in Spain and Greece), but are mostly happy to help.
  • At tapas, tell the waiter/barperson upfront you’re “sin gluten” or “sans gluten” (easier than “I’m grain-free”) and they’ll bring just meat and cheese and olives. This will generally cut out the deep fried crap, too (since most fried things are covered in breadcrumbs).
  • At tapas, if they bring chips, ask for nuts.
  • Watch out for gazpacho and other soups….they’re often bulked out with breadcrumbs.
  • Ditto some sausages.

A paleo confirmation

As I say above, getting enough greenery into your diet when traveling is possibly the biggest challenge. I struggle with the idea of not eating as many vegetables as I normally would. Back home I can get really cranky if I don’t get enough greenery into my gullet in a day.

But I’ve given in a little. Because, honestly, my health has not suffered from eating a lot less green stuff than I normally do. A cheese and meat and fat diet has worked for me. My health is great and I feel as though I’m brimful with vitamins and nutrition.


It reminds me of the experience of Canadian scientist Dr. Vilhjalmur Stefansson who lived for almost a decade eating meat and fat alone. He was an ethnologist studying the Inuit and had no choice…but it turned into an interesting experiment for him. His health didn’t suffer at all. In fact, it thrived. (You can read about his experiences here.)

Whatever. Fact is, it’s been good just to go with the flow and eat good, local, honest food that is prepared with love and tradition. Just without the bread.

Funnily, as you read this, I’ve left for Icaria, a small Greek island to join a National Geographic team who are looking into why so many of the inhabitants live over a hundred years. Icaria is one of Dan Buettner’s Blue Zones. And he’s returning to investigate the food their eating. I can’t wait to find out the secret…

Stay tuned!

Now I’m back online I’d be only too glad to answer any questions you have…on my travels…on the food…fire away!

Share this post