A vegetarian potato salad with creamy potatoes and crunchy veggies spiked with a bit of smoky paprika and vinegar. Green Olive and Egg Potato Salad makes that summertime BBQ, or picnic complete. This recipe is vegetarian and gluten free.
A Summer Essential
For the love of loaded potato salads! Never boring, always packed with flavor and endless possibilities. A true comfort food. They were always a part of BBQs, picnics and family gatherings, when I was a kid. It seemed those in the know had passionate opinions about what should and shouldn’t be in a potato salad.
Potato salads are serious business.
My Mam-Maw wouldn’t stray from her sour cream and mayo loaded baked-potato style potato salad, bacon included, while my Ma preferred a mustard-mayo base in her homemade potato salad. Always mustard. I’ve never really been too particular about potato salad, however. Even if it was majorly over-mayoed (mayo lover here). #getinmybelly
But since I started cooking and exploring food in my young adult life, stepping outside of my potato salad box has been quite the adventure. Potatoes are versatile and pair easily with a variety of flavors and textures. They’re a creamy canvas for creating a healthy potato salad masterpiece.
Green Olive and Egg Potato Salad is Rob’s favorite potato salad recipe. And, comes in at a close second for me, just under my beloved Southern style Texas Potato Salad recipe.
Recipe Inspiration
This vegetarian potato salad masterpiece comes from my friend, Mikel. He first introduced Green Olive and Egg Potato Salad to me a few years ago at a Memorial Day potluck. I was taken by the pops of briny olive throughout, creamy mayo base – because, HELLO (!!) mayo – crunchy veggies, creamy potatoes and eggs.
How to Make this Vegetarian Potato Salad Recipe
- First, put the potatoes on to boil. Meanwhile chop the veggies.
- Second, Dump potatoes into a large mixing bowl and add the apple cider vinegar. Refrigerator for 20 minutes.
- Third, cook the eggs in water to a hard boil.
- Fourth, whip up the easy dressing: mayo, vinegar, salt, paprika.
- Last, place all the ingredients in a large bowl and mix.
Plan on refrigerating for at least an hour so the flavors can marry.
A Few Recipe Notes
- What kind of potato to use? Use German Butterball, Yellow Finn or Yukon Gold Potatoes for this potato salad recipe and leave the skins on. The light color of the skin allows for the colors of the other potato salad ingredients to shine.
- Make ahead? Yes please! Make up to one day ahead! This potato salad’s flavor and ultimate creamy improves with a little time.
- Potatoes can take quite a bit of salt. Prior to serving and after allowing the salad to rest in the refrigerator for at least an hour, taste the salad and adjust salt and pepper to taste.
- The creamy factor of potato salad is completely adjustable to taste. If you find the salad needs a few more tablespoons of mayo, add it in at anytime after the salad is prepared. I’m known to give it a few more sprinkles of vinegar too.
More Potato Salad Recipes to Love
- Middle Eastern Potato Salad – from Floating Kitchen
- Texas Potato Salad
- Deviled Egg Potato Salad – from Foolproof Living
- Roasted New Potato Salad with Lentils and Herbs – from Occasionally Eggs
Green Olive and Egg Potato Salad
Ingredients
- 2 lb (930g) German Butterball or Yukon Gold Potatoes sliced into 1" cubes, skin on
- 3/4 tsp Fine Sea Salt
- 2 Tbs Apple Cider Vinegar
- 5 Farm Fresh Eggs
- 1 C (135g) Purple Onion medium dice (about one medium onion)
- 1 1/2 C (185g) Green Bell Pepper medium dice (about one medium bell pepper)
- 3/4 C (75g) Celery thinly sliced (about 4 celery stalks - chop the leaves and add them to the salad too if you have them!)
- 1/2 C (15g) Curley Parsley packed and chopped fine, reserve a few Tbs for garnish
- 3/4 C (100g) Green Peminto Stuffed Olives chopped + a few extra whole olives for garnish
For the Dressing:
- 1/2 C + 1 Tbs (150g) Mayonnaise I like veganaise or just mayo (adjust up or down to taste)
- 2 Tbs Apple Cider Vinegar
- 3/4 tsp Sea Salt
- 1/2 tsp Fresh Ground Pepper
- 1/2 tsp Smoky Paprika divided
Instructions
For the Potatoes:
- In a large stock-pot, add potatoes and cover with cold water filling to 2 inches (5 cm) above potatoes. Add 3/4 Tbs sea salt. Bring to a boil, reduce heat and simmer for between 8-15 minutes. Butterball potatoes take about 8-9 minutes and Youkon Gold take about 10-12 minutes to cook. Simmer until just fork tender, but not mushy. Drain.
- Dump potatoes into a large mixing bowl and add 2 Tbs of apple cider vinegar. Gently stir to incorporate the vinegar. Place in refrigerator for 20 minutes.
For the Eggs:
- While the potatoes are cooking, in a small sauce-pan, add the whole eggs and cover with 2 inches (5 cm) of water. Bring to a boil, remove from heat, and put lid on. Set aside and set timer for 12 minutes.
- Drain eggs, place in a small bowl, cover with cold water and allow to cool for 5 minutes. Peel eggs, dice and place in large bowl with potatoes. Set aside.
For the Dressing:
- In a small bowl, whisk together the mayonnaise, vinegar, sea salt, pepper and 1/4 tsp smoky paprika. Set aside.
Putting it all Together:
- Into the large mixing bowl with the potatoes and eggs, add the purple onion, bell pepper, celery, parsley and olives. Pour the dressing over the veggies and stir gently. Taste for mayonnaise and salt adjustment and add plenty of fresh ground pepper to taste. Store in the refrigerator for at least an hour prior to serving. Flavor development improves as the salad chills in the fridge. Spoon onto a serving dish/bowl and sprinkle with remaining paprika and garnish with whole olives and remaining chopped parsley.
I love the recipe my Husband does. Ot care for green bell pepper so I used red. DELICOUS can’t wait to take it to our Super Bowl Party!
Hi Penny! Thank you so much for your note and giving the recipe a go! So happy to hear you and your hubs are enjoying the recipe! – love the red bell sub BTW!
My mother-in-law introduced me to egg and olive sandwiches 40 years ago! I love it and still make them often. I can’t wait to make this salad!
I love that combo too… I hope you enjoy the recipe!
Green olive and egg potato salad… :) how did you get that idea of this delicious item. I made it and it was very tasty. Nice work man but I love to eat this salad with bread yo can also try it. it was great, believe me.
Hey Arunava! Thank you for coming back and leaving a note! This potato salad is the brain-child of my chef friend. I knew the first time I tried it I wanted to blog about it. So happy you enjoyed the recipe!
I have never eaten a potato salad with green olives! This salad looks like the perfect picnic salad, and I love the additional ingredients to make it healthy too! I am always mesmerized with your beautiful shots Traci! Great one :)
You’ve gotta try it Amisha! IT will change your potato salad eating world! LOL! xo
I just made this for an office 4th of July lunch. Wow, its absolutely delicious. What a change from the overly sweet mayonnnaised to death potato salad. Thanks so much for sharing the receipe. I made it exactly as printed. I wouldn’t add or change anything.
Oh my goodness, Elizabeth! Thank you for your note, coming back to leave a note and kind words… So happy to read your note. I’ll pass it on to Mikel! He’ll appreciate this!
I believe you left out the cider vinegar in the dressing directions.. I am assuming all 4 Tbsp. go in to the dressing? Or are 2 of the 4 on the potatoes when they are cooked and drained?
Hi Janette, you’re right – 2 Tbs for the potatoes and 2 Tbs for the dressing. I fixed it and thank you for pointing that omission out! I hope you enjoy the recipe!
Oh my goodness, Traci! This looks and sounds wonderful. The kind of potato salad I want! Especially with those green olives – so delicious!!
Thank you Tessa! The briny olives are a nice surprise!
Hi, Traci! Can’t wait to try this one. Sounds so good. What a neat idea for the olives.
Thank you Claudia! I hope you enjoy it!
I’m a sucker for a good potato salad and this one is right up my alley! Creamy with boiled egg and tangy olives- YUM. I want to have a BBQ now just so I can make this!
You and me both, Sarah! lol! I’d love to have a BBQ with you!
Yum, yum, yum – Potato salad is one of my favorite summer party sides – it’s always the first thing that I look for when I’m loading up my plate. Just love this combo – fully packed and loaded with goodness! Pinning! Hope you had a great weekend, Traci!
haha! Me too Geraldine… and then the next is baked beans! Thank you for your pin!
One of my favorite things about summer parties Traci! And all the years I’ve been making potato salad, I’ve never thought to add olives! Oh, what I’ve been missing! Such an awesome idea. I’ll most certainly be trying your recipe, so I’ll keep you posted! Happy weekend!
Potato salads are so good and this combo with green olives is so good. I didn’t grow up eating egg potato salad, but have fallen in love with them here. This would be so perfect for summer picnics.
Great job my friend.
O this looks amazing with the green olives. I have all the ingredients on hand so this weekend I am so making this!
Potato salads can definitely be a blank canvas for dressings and add ins. My Mom would have really liked this one. When I was little I remember watching her make a sliced green olive and mayo sandwich for lunch. I wanted to like it so badly but I was in camp black olive only back then. Now I’ll eat any and all olives… and potato salads!
Mayo Olive Sandwich!? Jean! That sounds SOOOO good!! Another mayo lover, no? Hooray for such a variety of olives! They all have their own unique flavor. I like that this is Mom approved!
Perfect, refreshing, vibrant; as usual :-) Thank you !
Thaaank you lovely!
Wow! Why didn’t I think of that? It stands to reason that green olives would be amazing in potato salad since I love them in my egg ‘n olive sandwiches! This recipe is a keeper, my friend! Happy weekend! xo
OMGeee, Annie! Did you say egg and olive sandwich?! I’m totally going to do that! Thank you for your tip, love! xo