Healthy meals and recipes for weight loss

The Best Creamy Potato Salad Recipe With Tips | Mustard Potato Salad Recipe With Eggs

creamy potato salad recipe with egg

Table of Contents

Mustard potato salad with eggs and crunchy vegetables.
creamy potato salad recipe with mustard

This creamy potato salad recipe with eggs brings back so many family meals for so many people and that is why I have been determined not to give it up, also when losing weight.


While classic potato salad has a very mayonnaise-rich dressing, this recipe plays more with the flavors of the ingredients, all brought together surely by some mayo, but also by some deep mustard and fresh olive oil.


Ready in very little time, this will surely become a family favorite, as it is not only healthy and colorful, it is also ridiculously tasty with a crunch!

potato salad ingredients


Let’s talk nutrition! 

Potatoes are one of the most popular vegetables in the world and not surprisingly so, as they are extremely versatile, affordable, and tasty.


This root vegetable is rich in nutrients and vitamins, such as Vitamins B and C, as well as potassium; a large amount of these nutrients is contained in the skin of the potatoes, so peeling them greatly affects the quantity.


It is important to carefully choose the cooking method of potatoes, like baking or boiling them should be preferred to frying them, as this method can add a lot of calories and fat.


easy potato salad recipe

Questions time!

How to make creamy potato salad? 

This recipe is very quick and versatile, as many ingredients can be swapped, added, or removed according to your taste.


Start by boiling the eggs and the washed baby potatoes in separate pans; to the boiling potatoes add a teaspoon of salt, as this will allow the salt to be absorbed, making the potatoes more flavorful and require less salt to be added later.


Once the tender potatoes have cooled down, chop them in quarters (or halves if small), and set them aside. For the eggs, ensure you do not overboil them, as the egg yolks may become green where they meet the egg whites, looking quite unpleasant; as soon as your eggs are cooked, place them in a bowl of cool water and allow them to cool down, before peeling them and chopping them.


To prepare the creamy dressing, mix the mayonnaise, olive oil, mustard, and black pepper, ensuring the oil is well incorporated into the other ingredients, as it will make it easier to coat the potato salad.


In a large bowl, add the cleaned and chopped red onion, celery, carrots, hard boiled eggs, and potatoes, then add the dressing on top and mix well using two large spoons; to avoid breaking the pieces of vegetables, insert the spoons on the side of the bowls and move them to the center, then lifting.


Serve and enjoy!

onion and celery
Thinly chopped onion and celery
carrots and egg
Add the carrots and egg
Boiled potatoes
potato salad dressing
Prepare the creamy dressing
Add dressing to the vegetables
healthy potato salad recipe
Creamy potato salad recipe

What are the best potatoes to use for potato salad? 

As potato salads require tossing and mixing, small waxy potatoes that hold their shape after being boiled are the best choice; the most famous ones for the job are red potatoes, Yukon gold potatoes, and yellow Finn. Another good option is Russet Potatoes (also known as Idaho), as they have a fluffy body and thick skin, all while having a high starch content.

How to boil potatoes for potato salad? 

Add the whole small waxy potatoes to a large pot and cover with plenty of water; cover the pan with a lid and bring to a boil. Once the water boils, add a teaspoon of salt and allow the potatoes to cook for about 15 minutes, or until they easily pierce with a fork. Allow the potatoes to simmer, not to boil, as medium-high heat will make the potatoes crash into each other and make them mushy; keep the flame to a level that the water just gently simmers.


Once ready, drain the water and place the potatoes in a large bowl of cold water for a couple of minutes, so to stop them from continuing to cook and to make them easier to handle quickly. Should you prefer to eat your potatoes without skin, this is very easy to remove by hand once the potatoes have cooked.

How to make perfect hard-boiled eggs for potato salad? 

To cook the eggs, place them in a pot and cover them with plenty of water; place a lid on the pan and bring to a boil; as soon as the water boils, remove from the heat but do not lift the lid from the pan. Allow the eggs to cook in the water for 9-12 minutes, depending on preference (mine have been cooked for 10), and, after the time has passed, move them to a bowl of cold water and allow them to cool down for 10-15 minutes; once cool, the eggs are ready to be peeled and chopped for the potato salad.


 ~~ If you love eggs, have a look at this absolutely delicious South Indian Style Coconut Egg Curry Recipe! Your whole family will love it! 

creamy potato salad recipe

How long does potato salad last? 

Freshly made potato salad can be stored in the fridge in an airtight container for up to three days.


 ~~ This salad is a great meal prepping idea! If you want to know more, have a look at How To Meal Prep? | 15+ Easy Healthy Meal Prep Ideas, Tips, and Recipes | Guide to Meal Prepping

What to serve with potato salad? 

This is one of many people’s favorite recipes and, because of its classic flavors, it is easy to serve with so many dishes! Keep it casual and serve this homemade potato salad during a barbecue, perhaps with a nice chicken burger or a chicken kabob.


Prepare it for a family dinner and serve it with a glorious stuffed chicken breast wrapped in prosciutto or with a simple chicken breast cooked with a creamy mushroom sauce.


This is the best potato salad recipe and it works perfectly also as a side for a picnic, where you could perhaps bring these chicken tikka baguettes as well.

Is potato salad gluten-free? 

While the whole ingredients in this recipe are gluten-free, the processed ones, such as mayonnaise, may contain gluten, so it is important to choose a dressing that is gluten-free and there are quite a few alternatives in the market. Sour cream is a great alternative to mayonnaise, however always ensure you read the label.

How much potato salad per person? 

This side dish recipe provides 8 medium-sized portions.

easy potato salad recipe

Here are some of the best substitutions and additions: 


  • Sour Cream: should you want to exclude the mayonnaise from this recipe, then sour cream is a great choice, as it is also extremely creamy and rich. Many like to mix mayo and sour cream for extra creaminess.


  • Tanginess: should you like some tanginess in your salad cream, then feel free to add some thinly chopped dill pickles or sweet pickles; another great way of achieving this light acidity is by adding a little white vinegar or apple cider vinegar, however also lemon juice works well. Most times, when going for a more tangy option, it is best to exclude the mustard, so as not to have too many strong flavors in the same recipe.


  • Red onions: should raw red onions be too strong for your liking, you can either soak them once chopped in some cold water for about ten minutes, or you can substitute them for some green onions.


  • Fresh herbs: feel free to add some fresh herbs to your salad! With this recipe freshly chopped parsley and dill work excellently, however, also chives are a good option.

A few notes: 

Here are some of my top tips for a great potato salad:


  • Large bowl: As you wouldn’t want to mash your cooked potatoes (nor the crunchy veggies), it is best to mix this potato salad in an extra-large bowl, with large spoons, inserting them from the sides and lifting from the bottom up.


  • Miracle whip: if instead of using light mayonnaise or sour cream you prefer miracle whip, go for it, however, you may need to balance the other ingredients, as this is pre-flavored with mustard flavors, dry garlic, and spices.


  • Yellow mustard: To offer it a different color and taste, I like to prepare this salad using whole grain mustard, however American yellow mustard works perfectly too.


  • Healthy recipes: remember to recalculate the calories for everything you add or remove, but most of all, try not to overdo it with the dressing, which is often full of added sugars, salts, fats, and all sorts of preservatives to make them last longer.


  • Whole potatoes: Baby potatoes have a thin skin that is full of nutrients, so I like to serve this salad with skin-on potatoes, however should you not like it, feel free to peel them.


This is a lighter take on grandma’s creamy potato salad recipe, yet all the flavor is still there. Enjoy it as a side dish during a barbecue or an evening meal, or use it for your lunch box… it always tastes good, because it is!

creamy potato salad recipe with mustard

The Best Creamy Potato Salad Recipe

Mustard potato salad with eggs and crunchy vegetables.
5 from 3 votes
Prep Time 20 mins
Cook Time 10 mins
Total Time 30 mins
Course Salad, Side Dish
Cuisine American
Servings 8 portions
Calories 105 kcal


  • 500 g Baby New Potatoes or preferred potatoes
  • 3 Eggs
  • 1 Red Onion
  • 1 Carrot
  • 2 Celery Sticks
  • 2 Tbsp Light Mayonnaise
  • 1 Tbsp Olive Oil
  • 1/2 Tbsp Wholegrain Mustard or American if preferred
  • Salt and Pepper to taste


Prepare the vegetables

  • Start by boiling the potatoes in plenty of salted water until they are easily pierced with a fork and ready; as soon as they are cooked, allow them to cool down and then chop them in halves or quarters.
  • Try chopping the next ingredients in about the same size so to allow them to mix better, in a more uniform way.
  • Boil the eggs and, as soon as they are cooked, cool them down in some ice water; once cool, peel them and then chop them.
  • Peel and chop the onion in small dice; should you find raw onion too strong, then soak it in cold water for about 10 minutes, then allow to dry, as this will remove the strong raw smell and taste.
    Alternatively, you can use spring onion.
  • Peel and chop the carrots; should you not like raw carrots, you can lightly boil them for 3-4 minutes, so to eliminate some of the crunch.
  • Wash and peel the celery, then chop it to size.
  • Put all of the chopped vegetables in a large bowl; choose a bowl that allows you to easily mix the salad, not one that just fits it.

Prepare the creamy potato salad dressing

  • In a bowl, mix the light mayonnaise, olive oil, mustard, salt and pepper until you reach a homogenous and creamy dressing.
  • Add the dressing to the vegetables and mix until all of the vegetables are covered with it; to do so and avoid mashing the vegetables, insert the spoons from the side of the bowl, then lift towards the centre.
  • Taste for seasoning and adjust if needed; serve and enjoy!


Calories: 105kcalCarbohydrates: 13gProtein: 4gFat: 4gSaturated Fat: 1gPolyunsaturated Fat: 1gMonounsaturated Fat: 2gTrans Fat: 1gCholesterol: 62mgSodium: 71mgPotassium: 335mgFiber: 2gSugar: 2gVitamin A: 1372IUVitamin C: 14mgCalcium: 24mgIron: 1mg
Keyword creamy potato salad, potato, potato salad
Tried this recipe?Let us know how it was!
Share on pinterest
Share on facebook
Share on email
Share on whatsapp

4 Responses

  1. Fabulous recipe. I didn’t tell my husband what was in it so he loved it. Love your recipes and your potato salad is no exception! I follow a vegan diet, but the rest of my family eats a regular diet.5 stars

Leave a Reply

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

Recipe Rating


My Personal Favorites

This opening statement, this blog… they have been a long time coming. 


While looking from afar, I am sure my life does not appear as anything else but ordinary (there were probably three moments that changed the course of my story), some choices I made I hope will encourage change for better health for others, as much as they have for me. 


As any well-respected story, this is how it starts… 


Once upon a time in the late ’80s… 


But that would make this page way too long and way too boring, so flash forward… 




Get our latest recipes and posts in your inbox. You won’t regret it!

Follow Us