Melbourne Paleo Food Safari

IMG_5534Last week I traveled to Melbourne to explore some of the many fantastic eateries and restaurants in the Victorian capital. Having lived in Melbourne a few years ago, I know my way around and love to jump on a tram and literally zigzag my way around. Melbourne is a bit of a grid which makes finding your way around easy, however finding the best places to go is not so easy. Some of the best places on offer are often down alleyways and in places that you’d least expect. Even after living in Melbourne barely five years ago, the social scene changes so quickly, with new cafes and bars popping up all over the place.

I half planned my weekend to make sure I could get to a couple of places on my list, and I left the rest open to see what I could find.

Challenge #1 – finding a paleo meal at the airport

I had an early flight on the Friday morning. I took a gamble and deliberately skipped eating at home to see how hard it would be to find a suitable healthy paleo option at the airport – something many people would be challenged with when traveling. Most of the food outlets in the airport terminal seemed to serve wheat and gluten-based meals like muffins, toast, pastries and the like, but I managed to find one place that had a selection of breakfast options including bacon, mushrooms (cooked in butter) and roasted tomato. They also had scrambled eggs however these were pre-made with cream so they were off the list. They didn’t have any green vegetables like spinach – this would have rounded the meal out nicely. The only other paleo-friendly options I found were a fruit salad (without yoghurt) and a packet of nut mix. That was it! But I was thankful for the breakfast of bacon, mushies and tomato. Someone also gave me a good tip on the facebook page – you can also get a half BBQ chicken and salad from Red Rooster at the airport, which makes for a nice paleo meal. I’ll keep this in mind for when I’m traveling during the day or evening. Thanks Adam for the tip :)

Challenge #2 – eating with colleagues who had no idea about my dietary requirements


I spent the day on Friday working out of my company’s Melbourne office, and my colleagues decided to go to an up-market pub for lunch. Its menu was mainly burgers and American-style food which was far from paleo. Unfortunately they had a limited menu available for lunch, and my best option was to order two sides – the salad and the steamed vegetables (which turned out to be mostly beans, not so paleo). I missed out on protein and I was pretty hungry that afternoon. But, I’m starting to realise that sometimes going hungry is better than eating something that will only leave me feeling bloated, flat, fatigued or any of the other symptoms I can experience when I stray from the paleo diet.

Challenge #3 – fine dining with friends on a set menu

My friends and I had a reservation at a popular restaurant called Chin Chin on the Friday night. The only way you can get a reservation is if you have 10 or more people which we did, however it’s a set menu. From experience, explaining the paleo diet to a restaurant is really difficult and makes me feel quite anti-social. I really don’t like taking away from the overall experience of dining with friends and I always do my best to accommodate my dietary requirements with as little hassle as possible. I love sharing good food with friends and family, and to me this also means sharing the same food. So I try to eat the same food even if I have to make small exceptions sometimes.

The restaurant was really good in adapting the set menu to provide a gluten and wheat-free variation for me. There wasn’t really much dairy so I didn’t bother asking for dairy free as well. Most meals were fine for me. One of the dishes was Pork Rollups with a flat bread, and they provided lettuce leaves for me so I could still enjoy the delicious pork. Some of the other dishes included kingfish with kaffir lime, grapefruit, coriander, ginger, salt and pepper squid, BBQ red salmon, barramundi papaya, beef ribs and soft shell crabs. It was finished off with a couple of desserts – one was a coconut rice dish and the other was a layered gelatinous dessert served in a martini glass. They certainly looked amazing (and yes I did have a taste…when in Rome, or in this case Melbourne haha!)

Chin Chin on Urbanspoon

Palate Restaurant Bar, Prahan – Melbourne’s only Paleo Restaurant

IMG_5515On Friday I caught a tram out to Prahan to try a restaurant called Palate, which has specific paleo menu options. I was really looking forward to dining here and I was sorry I couldn’t have more than one meal because there were so many options!

I settled on an amazing Bread Free Brekky Burger and a ‘Chocochia’ smoothie (dairy-free and paleo-friendly). Both came out quickly and the staff were really friendly and interested in my blog which I told them about after showing particular interest in the paleo menu items.

Palate seems to be a popular spot for paleo eaters, particularly the CrossFit community as I overheard two patrons talking about how much they could dead-lift :) It was a really nice place to spend a chilled Saturday morning. The breakfast menu is also available all day – and with paleo options including the bread free burger, omelette, a paleo muesli  and cauliflower rice risotto it’s worth checking out for breakfast or lunch.

Palate on Urbanspoon

My meal filled me up for most of the day which was great because my friends and I were heading to the football at the MGC that afternoon. Food at the football really hasn’t gotten any better over the years. I really don’t understand why it’s so bad! The options are still pies, chips and this time I did notice that there were also Crust pizza’s on offer, although none were gluten free. Considering how long an AFL match goes for, it’s worth considering packing a few paleo snacks to avoid eating disappointing fast food. I did get a little hungry towards the end and snacked on some not-so-pure-paleo hot chips.

Builders Arms Bistro, Fitzroy – Rotisserie Roast every day of the week

IMG_5548On Saturday night we had a reservation at the Builders Arms Bistro. It’s a cosy and modern pub in Fitzroy, offering both casual and fine dining options. We decided to dine in the Bistro, although they also have a fine dining restaurant called Moon Under Water. The Bistro has some fantastic menu items, including a Rotisserie with a different roast meat option every day of the week. I thought I was already sold on this (Saturday night’s Rotisserie was Spit-jack Chicken and Chips, the Suckling Pig is offered on Tuesday BTW!) but that was before I heard about the Roast Pork Shoulder, which is shared between 3-4 people and takes an hour to be served. To my delight, three of my friends were also keen on the pork so we decided to order a few starters to keep us going while we awaited a feast for the eyes (and stomach). It was an amazing meal, served with apple sauce and a fennel and lemon salad. It’s worth waiting for if you find yourself here for dinner.

Builders Arms Hotel Bar and Bistro on Urbanspoon

Stokehouse Cafe, St Kilda – Sunday brunch by the sea

IMG_5577On Sunday morning my friends and I had reserved a table at Stokehouse Cafe, a hip looking cafe/restaurant by the water in St Kilda. Although not a huge amount of paleo options on the menu, it was a good choice for a larger group. I created a paleo-friendly meal by ordering the Smoked Ocean Trout (without the toast) which came with a slow cooked 63 degree perfectly poached egg (amazing!) and some chorizo. It was delicious, but a little small with the bread removed.

Stokehouse Cafe on Urbanspoon

After brunch, an afternoon shopping spree on Chapel Street was the chosen activity by my friends and I. After accidentally buying a pair of Italian leather boots (whoops!) I found myself wondering around the Prahan Markets, a place I’d go almost every weekend to pick up fresh produce when I lived in Melbourne. Although it has some fantastic fresh food, like the colourful radishes I photographed, it also has an abundance of delis and bakeries – places I used to visit before embarking on my paleo lifestyle a few years ago. I found a van in the outdoor eating area that served fresh mussels cooked in a range of broths, but I wasn’t hungry enough to justify eating another meal so I took a mental note for next time I’m there.

Not-so-yum cha

Later that afternoon my friends were keen on a late Yum Cha before flying back to Sydney that evening. I knew this was going to be a challenge, and in the end it just proved too difficult to find suitable options at Yum Cha, without guaranteeing that I wasn’t going to be feeling it later! Unfortunately this was one time when I had to leave my friends to their dumplings and find another option.

IMG_5585In a desperate dash to find a paleo-friendly meal, I found myself in the Greek Quarter of the Melbourne CBD. It was raining (true to form of Melbourne’s reputation for having four seasons in one day) so I ran into a Greek souvlaki restaurant. Lamb and chicken cooked on a spit is a great paleo option when you’re out and about or on the run, and so I ordered a mix of both with a fresh Greek salad. Although it came with chips, the meat and salad were a saviour!

This marked the end of my food safari around Melbourne. It reminded me of just how many fantastic food options there are and I will definitely be heading back soon. I think a trip down South at least every six months is definitely worthwhile.

Back in Sydney this week and feeling a little fatigued from all the dining out, I tried to get back into the rhythm of home cooking and eating fresh, whole foods. Nearing the end of the 30 Days of Pure Paleo Challenge, although I didn’t really need to adjust my eating too much given I eat a paleo diet 90% of the time, it’s served as a reminder of why I changed my diet and lifestyle in the first place. To eat to live and live to eat. Eating to live means eating only when and what I need. And living to eat means enjoying each and every minute of the food I choose to nourish my body with.

I look forward to sharing my experiences next week from the final week of the 30 Days of Pure Paleo Challenge, including the Paleo Foodies Dinner at the Local Taphouse this Thursday, where I’ll be showcasing just how good paleo dining can be.

Until next time.



Alison Sims

Passionate about real food and healthy living, Alison Sims is the founder and author of Paleo Foodies. She is on a mission to discover the best paleo dining in Australia and all around the world. What started as a part time blog in 2013 has lead to a full time career for Alison, who previously spent a decade in Advertising and Marketing. She is now a regular contributor to health and lifestyle publications, a public speaker in food and health, and co-publisher of Paleo Foodies Magazine.


  • Reply January 31, 2014


    Great article! I also don’t mean to alarm you, but BBQ chicken is not gluten free. I used to have terrible reactions to it.

    • Reply January 31, 2014

      Ali @ Paleo Foodies

      Hi Hayley, thanks for the tip and glad you liked the article! Yes it’s always worth checking especially if you have an allergy.

  • Reply April 6, 2014


    All your stuff is great Alison but this article was particularly awesome. Had a weekend in Melbourne and hit up Palate and Builders Arms. Both were excellent (had the pork shoulder too at builders arms which was sensational). So yeah, a big well done!
    Cheers, Chardy

    • Reply April 8, 2014

      Alison Sims

      Good to hear Chardy! I was in Melbourne over the weekend too and I discovered Top Paddock (excellent breakfast / brunch spot in Richmond) and Third Wave – which has a full paleo menu! I’ll be doing a write up of Third Wave this week so watch this space. Thanks for the positive feedback :)

  • Reply December 29, 2014


    Hi Ali,
    Great to find your blog.
    I wondered, if you worked in the CBD and were sufficiently time-poor to not have the opportunity to prepare your own lunches… did you have any recommendations for Paleo-friendly (and cheap) lunches in the Melbourne CBD?

Leave a Reply

Share on

Tweet about this on Twitter0Share on Facebook5Pin on Pinterest43Share on Google+0