Whole30 Potato Salad

Jump to Recipe

This post may contain affiliate links. Read our disclosure policy.

A Whole30 Potato Salad that will help you keep your healthy eating goals during the summer picnic season. It’s creamy, homemade seasoned mayo dressing boosts this healthy potato salad’s flavor.

I grew up on potato salad. You can find our family’s classic potato salad recipe here. That salad has been the centerpiece of nearly every summer family picnic that I can remember. And that delicious potato salad is the basis for this Whole30 potato salad.

By the way….did you catch the first paleo side dish I shared with you last week? It was Paleo Broccoli Slaw and you all seem to be loving it as much as I do!

pan with potato salad

This Whole30 side dish recipe is perfect for potlucks, picnics and family gatherings. We make this for our church small group often and everyone loves it. It allows you to stick with your eating goals without making a fuss.

Can you eat potatoes while on Whole30?

Yes! You can eat white potatoes in moderation while participating in a Whole30.

I didn’t specifically call this side dish “paleo” because I know that some of you paleo folks are dead set against white potatoes. Since Whole30 approved white potatoes several years ago, I decided to label this healthy potato salad recipe as “Whole30” and secretly calling it paleo potato salad at home. And if there is ever a Whole30 comfort food…this is it!

And can we just celebrate Whole30 potatoes for a second?!

Healthier Potato Salad

So what changes did I make to our classic potato salad to make it healthier?

  • Leave out the sugar. Our original recipe only called for 1 tablespoon, and I’m finding that when I leave the sugar out of some of my favorite family recipes, I don’t miss it.
  • Make my own mayonnaise. I tried many different mayo recipes and techniques, but when I found this Fool-Proof Homemade Mayonnaise recipe, all searching stopped. You may think making your own mayo is too much trouble, but this literally takes 2 minutes. Put the ingredients in a glass jar, use an immersion blender to blend, and in 30 seconds, you have a creamy, homemade mayo that is sugar free and so much healthier than store-bought mayo.

And really? That is the only changes I made to my long-time, much-loved potato salad recipe.  

making homemade mayonnaise

What is the best potato to use for potato salad?

Did you know it is important to choose the right potato for each recipe? Not all potatoes are created equally!

For potato salad, you’ll want a potato that is waxier and lower in starch. This will help the potato hold it’s shape during cooking and mixing and not turn into mashed potato salad.

For potato salad, choose red potatoes. You can also choose Yukon Gold potatoes.

red potatoes on a cutting board

How to Make Potato Salad

The first step in making potato salad is preparing the potatoes. We peel the potatoes, although some choose not to. It’s really a matter of preference. With red potatoes, the skin is thin so you won’t notice them too much.

After you peel the potatoes, chop them into 1″ cubes. Make sure they are about all the same size so that the potatoes will cook evenly.

chopped red potatoes

How to Boil Potatoes

We find it easiest to boil potatoes on the stovetop. Simply add the potatoes to a large pot, cover the potatoes with water (1″ of water over the potatoes), then place the pot on medium high heat to boil.

How Long to Boil Potatoes for Potato Salad

The potatoes will need to boil for about 15 minutes. This time starts after the water comes to a boil, so plan for about 20-25 minutes total.

The potatoes should be fork tender, but they will continue to soften slightly as they cool so don’t overcook them.

After the potatoes are done, drain them and rinse with cold water to help them cool down.

Hard Boiled Eggs for Potato Salad

If you want to save a step, throw the raw eggs into the boiling potato water and they will hard boil right alongside the potatoes cooking.

We usually make up a big batch of instant pot hard boiled eggs. They peel beautifully this way.

diced potatoes in boiling water

Potato Salad Dressing

While the potatoes are cooling you can prepare the dressing. Simply mix the dressing ingredients together. It’s quick and easy!

**Pro Tip: If you are making the dressing up much in advance, place a piece of plastic wrap over the top and press down so it covers the top evenly. This will help prevent the dressing from drying out.**

ingredients for potato salad in a bowl

What do you add to potato salad?

I love just adding hard-boiled eggs and cucumber to my potato salad. Feel free to add celery, onion, grated carrot, or any other favorite veggies.

Note: Be sure to wait until the potatoes are cool to add any veggies. If the potatoes are warm, it can cook the veggies, making them soft instead of crunchy.

celery, carrots, cucumber and onion

Kid Friendly Healthy Salad

So the question is always…what did the kids think? Let’s just say that I didn’t even know they liked potato salad. There was a bit leftover potato salad that I was looking forward to having for lunch one day last week. When I went to the kitchen to eat lunch, the kids had already devoured the potato salad. Completely gone. Bowl wiped clean. So yeah…it’s safe to say it is kid-approved!

Frequently Asked Questions

Can you freeze potato salad?

Yes, you can, but we don’t recommend it. The vegetables can get mushy and the dressing can separate. We don’t recommend freezing our potato salad.

How do you store potato salad?

Because potato salad has an egg based dressing, you want to refrigerate it in an airtight container. Remove it from the refrigerator right before serving. If you are carrying it to a potluck, make sure you pack it in ice to keep it cold. Potato salad should not sit out for more than 30 minutes at room temperature.

How long does potato salad last?

This potato salad is best eaten within 3 days.

How much potato salad per person?

Planning for a party? You’ll want to plan for about ½ cup of potato salad per person. If you aren’t having many other side dishes, you may want to plan for up to ¾ cup per person.

Does potato salad have dairy?

This potato salad is dairy free! If you use another potato salad recipe, there may be dairy in the dressing so watch closely.

A bowl of Potato Salad


buy now button

ONLY $4.99!

healthy Whole30 Potato Salad
healthy Whole30 Potato Salad

Whole30 Potato Salad

4.82 from 11 votes
A Whole30 Potato Salad that will help you keep your healthy eating goals during the summer picnic season. Seasoned mayo boosts this fresh salad’s flavor.
Servings 10
Prep Time 30 minutes
Cook Time 15 minutes
Total Time 45 minutes

Email Me This Recipe!
Enter your email and get the recipe sent to your inbox! Plus you’ll get new recipes from us every week.


  • 8 large red potatoes (we've done up to 5 pounds of potatoes with this amount of dressing)
  • 6 large eggs
  • 1 1/3 cup homemade mayonnaise
  • 1 tablespoon vinegar
  • 1 teaspoon pepper
  • 2 teaspoons salt
  • 1 tablespoon mustard
  • 1 cup sliced and quartered cucumbers
  • Optional: chopped onions, celery or carrots


  • Wash, peel and cut potatoes into bite-size pieces. In a large pot, bring water to a boil. Add potatoes and cook until the potatoes are tender. Drain the potatoes and put them in a big bowl.
  • Put the eggs in another saucepan and add water to cover them. Bring the water to a boil, and then let the water and eggs boil gently for 5 minutes. Drain the eggs and cover them with ice cold water. Allow the eggs to sit in the cold water while you mix up the dressing.
  • For the dressing, combine the salt, mustard, mayonnaise, vinegar and pepper. Mix until completely combined. Set aside.
  • Once the eggs are cool enough to touch, drain the water. Peel the eggs and dice them, then add them to the potatoes. Pour the dressing over top the eggs and potatoes and mix until the potatoes are covered.
  • After the salad is completely cooled, add the diced cucumber. If you add this while the potatoes are still warm, it will soften the cucumber. Add in the onions, celery and carrots, if desired.
  • Refrigerate until ready to serve.



*To use fewer pans and save a bit of time, boil the eggs in the same pan as the potatoes.
The calories shown are based on the recipe serving 10, with 1 serving being 1/10 of the salad. Since different brands of ingredients have different nutritional information, the calories shown are just an estimate. **We are not dietitians and recommend you seek a nutritionist for exact nutritional information.**


Calories: 374kcal | Carbohydrates: 28g | Protein: 8g | Fat: 26g | Saturated Fat: 5g | Cholesterol: 139mg | Sodium: 751mg | Potassium: 846mg | Fiber: 3g | Sugar: 3g | Vitamin A: 225IU | Vitamin C: 15mg | Calcium: 40mg | Iron: 2mg
Course Side Dish
Cuisine American
Calories 374
Keyword best potato recipes, healthy side dish, whole30 recipes
A bowl of food, with Potato Salad
About JulieJulie Clark

About Julie Clark

I'm Julie Clark, CEO and recipe developer of Tastes of Lizzy T. With my B.A. in Education and over 30 years of cooking and baking, I want to teach YOU the best of our family recipes.

Get 5 Classic Recipes with a Deliciously Secret Twist

You might also like

Join the Discussion

Notify of

Inline Feedbacks
View all comments

1 year ago

I had cucumbers in a creamy pasta salad and will never do it again – after a day the cucumbers became watery like – is there a way to prevent this from happening.
Also I want to make your dressing – but yours has mustard in in – the amount you put in – can one taste the mustard or can it be omitted- when I make a potato salad- I add baby garlic dill pickles and some pickle juice to the dressing 🤤🤤

6 years ago

Do you have to add the mayo/dressing to the potatoes while they are still warm? I often make enough extra boiled potatoes to have leftovers for something the next day. Thanks in advance.

6 years ago

I thought no vinegar for whole30?

7 years ago

What kind of potatoes and 8 potatoes is how much in pounds?

Greg Johnson
7 years ago

Potato salad is one of my summertime favorites. I never made it before, but was aware that only some of the ones I have sampled fit my taste buds as delicious. I didn’t know the ingredients for those favorites. I found it. This is it. Very simple. Potatoes, eggs, mayo, cucumbers. I added half an onion chopped and a couple stalks of celery. I have no idea why someone would want to add sugar to this. I was prepared to miss the sugar in the recipe and planned to add apple sauce. No need for sweetening this. You’ll ruin it.… Read more »

8 years ago

Why are you calling that potato salad a whole30 recipe. You are not allowed to have potatoes on whole 30