• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar

The Movement Menu logo

  • All Recipes
  • Whole30 Recipes
  • Paleo Recipes
  • Meal Plans
menu icon
go to homepage
  • All Recipes
  • Whole30 Recipes
  • Paleo Recipes
  • Meal Plans
overhead of patatas bravas recipe with tomato garlic aioli and fresh parsley
search icon
Homepage link
  • All Recipes
  • Whole30 Recipes
  • Paleo Recipes
  • Meal Plans
overhead of patatas bravas recipe with tomato garlic aioli and fresh parsley
×
Home » All Recipes » Dairy Free Recipes

Patatas Bravas Recipe

Modified: Sep 21, 2019 by Monica Le · Published: Mar 24, 2019 · 4 Comments

402 shares
  • Share
Jump to Recipe Pin Recipe
overhead of patatas bravas recipe with tomato garlic aioli and fresh parsley

I've got a very popular Spanish-inspired patatas bravas recipe for you, and it is absolutely fantastic! I've made this traditional Spanish tapa into a really tasty gluten free, dairy free and paleo version with a Whole30 compliant tomato & garlic aioli!

 roasted potatoes on a baking sheet

Is it a traditional play on patatas bravas?

This patatas bravas recipe is not fried which is typically how this tapas dish is served overseas. That doesn't mean it isn't *just* as delicious though.

This tapa is typically made with white potatoes, and they are cut into irregular cube shapes. They are then fried in oil and served with some sort of mayonnaise or tomato sauce.

I have been making roasted potatoes the same way for years, and I thought it was finally time to create something truly magical with them.

I knew that my homemade paleo mayonnaise would make an awesome base for the sauce, so that's when I started experimenting...!

patatas bravas on a circular plate

How to make the paleo mayonnaise base for tomato garlic aioli

That mayo recipe has been tried and true for years. You really have to make sure you are using the proper equipment though!

I use a jar that is very slightly wider than the base of the immersion blender. You let all of the ingredients settle for about one minute.

Then, you take the immersion blender and let it touch the bottom of the container, piercing the egg yolk completely. Turn it on and leave it on the bottom for about 20 seconds, until the whole bottom has turned white in color.

Very slowly lift it up to continue emulsifying. This process should take anywhere between 30 seconds to 1 minute. Continue blending until the mixture has thickened to your desired amount.

Stir in the salt and gently fold in the lemon juice. Store in an airtight container in the refrigerator for up to 10 days. However, for this recipe, we are going to need in a few more things- check out the instructions in the recipe card! 🙂

platter of patatas bravas with tomato garlic aioli on the side

To tell you the truth, Tim and I have been chatting about returning to Spain ever since we got back last April. it is our favorite place we've ever visited, and there are a few reasons why.

My opinion may be a little bit biased since we went while I was pregnant, and I absolutely enjoyed my pregnancy through and through. However, Tim was *not* pregnant, and he wants to return as well.

I think we felt more immersed in the culture than we normally do during international travels since we were able to communicate effectively. People were impressed with our Spanish speaking and understanding skill sets and wanted to welcome us.

More paleo potato recipes like this:

Buffalo Paleo Potato Salad

Whole30 Sweet Potato Hash

Dairy Free Whole30 Potato Salad

Spiralized Sweet Potato Fries

a tray of roasted potatoes with a jar of mayonnaise and a spoon

That being said, there are so many places we're eager to travel to, and we probably should check out those places for the first time before we do a round two in España.

We are in the midst of planning a family reunion (on Tim's side) in Montreal for later this year which is super exciting, but let's get back to this patatas brvavas recipe for now... 😉

How can potatoes that aren't fried taste so darn crispy and delicious?

The oven temperature and timing is key. I like to throw the broiler on low for a few minutes at the end to really make sure those taters are crunchy throughout.

I highly recommend eating these potatoes fresh. Sure, you can reheat them over low heat in a frying pan another day, but nothing is quite the same as fresh patatas bravas, you know!

a close up shot of patatas bravas on a platter

These patatas bravas really take me back...

I cannot wait for you to try these patatas bravas. Eating this dish really takes me back to such a fun and exciting trip that we got to explore so much during.

Isn't it insane how eating different tastes and textures can evoke memories wrapped in nostalgia? And so vividly, too?

For me, food and music are my biggest triggers. They are also the two things that move the needle for me most in my personal life. I've always been very much into exploring around musically.

Now, that I'm a foodie too, it's like a ridiculous amount of nostalgia and joy that can potentially be unlocked at all times.

patatas bravas drizzled with sauce on a plate

Well, what are you waiting for? I cannot think of anything better alongside breakfast or as an appetizer or snack than this patatas bravas recipe.

You are going to absolutely love it and keep coming back to it and over and over again.

I've actually made this tomato garlic aioli three times since making the potatoes. We've been eating it with our eggs in the morning, dipping roasted veggies in it, etc.

Happy cooking! Yummmm. 🙂

Patatas Bravas Recipe (Gluten Free, Dairy Free, Paleo)

Monica Stevens Le
I've got a very popular Spanish-inspired patatas bravas recipe for you, and it is absolutely fantastic! I've made this traditional Spanish tapa into a really tasty gluten free, dairy free and paleo version with a Whole30 compliant tomato & garlic aioli!
5 from 8 votes
Print Recipe Pin Recipe Add to Collection Go to Collections
Prep Time 10 minutes mins
Cook Time 30 minutes mins
Total Time 40 minutes mins
Course Appetizer, Side Dish
Cuisine Mexican
Servings 6
Calories 463 kcal

Ingredients
  

Tomato Garlic Aioli

  • 1 cup Homemade Paleo Mayonnaise SEE NOTES
  • 3 garlic cloves sliced
  • ¼ cup tomato paste

Potatoes

  • 3 pounds Yukon gold potatoes or red potatoes, sliced into 1" cubes
  • ¼ cup avocado oil
  • kosher salt to taste
  • black pepper to taste
  • fresh parsley chopped, for garnish

Instructions
 

  • Preheat the oven to 425 degrees Fahrenheit and adjust the oven rack to the middle position. Line two baking sheets with parchment paper and set aside.
  • Add garlic cloves and tomato paste to the paleo mayonnaise base. Blend using an immersion blender until by moving it up and down slowly until smooth and creamy throughout. Taste for seasoning and set aside.
  • In a large bowl, mix the potato cubes with the oil using your hands or a spoon until they are evenly coated.
  • Spread the potatoes onto both parchment lined baking sheets. You will want to make sure they have some room and are in an even and flat layer on each sheet. Depending on the size of your oven, you may need to make these in two batches. You can alternatively put one baking sheet on a lower rack and move it up higher once the potatoes above are finished cooking.
  • Bake at 425 degrees Fahrenheit for 25-30 minutes until they begin to turn golden brown. Turn the oven to a low broil for 4 minutes, flipping the baking sheet 180 degrees halfway through.
  • Remove the potatoes from the oven and transfer to a serving platter to slightly cool. Serve with tomato garlic aioli and chopped fresh parsley.

Notes

This is the base (paleo homemade mayonnaise) for the tomato garlic aioli recipe!

Nutrition

Calories: 463kcalCarbohydrates: 33gProtein: 6gFat: 33gSaturated Fat: 4gSodium: 322mgPotassium: 1053mgFiber: 6gSugar: 1gCalcium: 75mg
Tried this recipe?Let us know how it was!

More Dairy Free Recipes

  • muffins topped off with a white glaze and chopped pecans on a wire rack
    The Best Gluten Free Cinnamon Muffins
  • holding a frozen mangonada with a glass straw
    The Best Mangonada (Frozen Mango Margarita) Recipe
  • holding a kiwi cocktail with a fresh kiwi slice on top
    The Best Frozen Kiwi Cocktail
  • a frothy paloma in a coupe glass with a grapefruit wedge
    Frothy Grapefruit Paloma

Reader Interactions

Comments

    5 from 8 votes (7 ratings without comment)

    Leave a Reply Cancel reply

    Your email address will not be published. Required fields are marked *

    Recipe Rating




    This site uses Akismet to reduce spam. Learn how your comment data is processed.

  1. Jess says

    January 15, 2022 at 5:41 pm

    I think this may be the first comment that I’ve ever left on a recipe, which is crazy because I’m always cooking things I find online. This is absolutely delicious. Like the best thing ever. I tossed my potatoes in a little ghee. Added radishes to bulk it up. The fresh parsley is a must. It was so so so good. This is my new whole30 fave.

    Reply
    • Monica Stevens Le says

      January 20, 2022 at 12:29 pm

      This makes me so, so happy to hear. It's the tomato garlic aioli for me... right?? 😀

      Reply
  2. Melissa Dreifuss says

    April 29, 2020 at 8:45 am

    This tomato garlic aioli is out of this world. After I made it for the first time, my husband asked if it could be in the fridge at all times!

    Reply
  3. Erin says

    April 02, 2020 at 9:22 pm

    These were so delicious! I love potato anything but add in this garlicky sauce and you have my heart forever!5 stars

    Reply

Primary Sidebar

As Seen In...

As seen in popular media
Matt

Hi! I’m Matt!

I am a writer, father, and food lover. I am a real food cook and love to create delicious food that supports health and fitness. I’m so happy to welcome you to The Movement Menu. Read More…

Footer

overhead of patatas bravas recipe with tomato garlic aioli and fresh parsley

Get FRESH ideas for high protein meals!

Get 32 High Protein Recipes. Breakfast, Lunch, Dinner, & Dessert.

Subscribe to my newsletter and get the free full-color recipe book. With these recipes, you’ll have everything you need to eat healthy, hit your protein goals, and stay on track - all without spending hours in the kitchen.

I will not spam you. Newsletters sent out every 1-2 months contain new recipes and healthy eating news. Unsubscribe anytime.

Recipes

  • All Recipes
  • Whole30 Recipes
  • Paleo Recipes
  • Meal Plans

Recipe Management

  • Your Recipe Collection
  • Shopping List

More Goodies

  • Articles / Blog
  • Subscribe
  • Contact

Small Print

  • Privacy Policy
  • Affiliate Disclosure
  • Site Map

The Movement Menu by AIM Retail Partners, LLC is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com.

402 shares

Rate This Recipe

Your vote:




A rating is required
A name is required
An email is required

Recipe Ratings without Comment

Something went wrong. Please try again.