Heirloom Potato Salad with Vegenaise®

Vegan potato salad recipe made with tiny heirloom pink, purple and yellow potatoes and vegan mayo
A super easy potato salad with tasty heirloom spuds. Vegan and egg-free.

I snatched up a bag of those cute little potatoes at the market yesterday. You know the ones I'm talking about. Those baby sized spuds as cute as a button. In Easter egg colors like custard and purple and pink. So sweet and adorable you want to cradle the bag and speak in your talking-to-kittens voice. Heirloom root vegetable deliciousness. Yeah, you shell out a little extra cabbage for these pretty babies, true. But I say, live a little.

Indulge in excellent ingredients.

You only got one life. 

How many summers have you got left? How many picnics are allotted you? How many potato salads? If you don't subscribe to reincarnation, the answer is, too few. And if you do trust in the belief that you're destined to come around this way again, what's to guarantee you'll even be making potato salad? Maybe you'll be reborn into a village where noshing on nightshades is considered hellacious. You could be scorned. Forced to wear a giant red P stitched to your garment for the cursed Potato Eater moniker (that is, if you're born into an English speaking clan who uses the letter P and sports garments at all; if not my Darling, the alternative might involve a tattoo and an all together different alphabet). In other words, you know what you got. Even though we all, I'm sorry to tell you, forget this. Chronically.

We have today.

Or more accurately, we have NOW. This moment. So when these buttery creamy little roots show up at your market, you should only do one thing (yes, I used the word should, so sue me). Get a bag of these delightful petite spuds and make this super easy vegan potato salad. You won't be sorry. You'll be happy.

Which, in my book, is worth its weight in gold.

Vegan potato salad recipe made with tiny heirloom pink, purple and yellow potatoes and vegan Vegenaise mayo
My lunch today. Heirloom potato yum.

Easy Vegan Heirloom Potato Salad Recipe

The smooth- and dare I say- buttery taste of these tiny heirloom potatoes needs almost no seasoning. Seriously. I didn't add anything that might overpower their distinctive fresh potato flavor. You can always add a little diced red onion, if you like. But I suggest letting these potatoes shine. Try only sea salt and a touch of lemon juice before you add onion (or any other strong seasonings you may habitually reach for). A dab of Vegenaise® to moisten brings enough creaminess to this simple summer salad.


1 bag heirloom potatoes in multi-colors (roughly enough to feed four)
Sea salt and ground pepper, to taste
Fresh lemon juice, as needed
Vegenaise® or your favorite vegan eggless mayo*
Fresh chopped parsley


Scrub the little potatoes and slice them into half-inch pieces. Toss them into a pot and cover with fresh cold water. Add a dash of sea salt. Cover and bring to a boil. Lower the heat to a constant high simmer and cook the potatoes until they are fork tender. This doesn't take long- maybe 15 minutes or so. Don't over-cook them till mushy.

Drain the cooked potatoes.

While they are still warm, dump the potatoes into a bowl and season with sea salt and ground pepper, to taste. Sprinkle with a little fresh lemon juice (or use a light, mild vinegar if you prefer) and toss to mix. Add in a spoonful of the Vegenaise® and mix gently. Start with a little- and add a little more if you need it. I find a little goes a long way. Use enough to moisten, but don't make the potatoes swim in it.

Add in fresh chopped parsley, to taste.

Cover and chill for an hour, till serving. Before serving, taste test and adjust seasonings if necessary- more sea salt, pepper, or eggless mayo, etc.

Serves 4.


Browse all my potato salad recipes here.

 photo Print-Recipe.png

Recipe Source: glutenfreegoddess.blogspot.com

All images & content are copyright protected, all rights reserved. Please do not use our images or content without prior permission. Thank you. 

More spud love from food bloggers:

Japanese Style Home Potato Salad at Book of Yum
Grilled Sweet Potato Salad at Kalyn's Kitchen
Roasted Potatoes with Lemon Thyme Vinaigrette at The Perfect Pantry
Potato-Green Bean Salad with lemon and Basil at FatFree Vegan Kitchen
Potato Salad with Summer Herbs and White Wine Vinaigrette at Andrea Meyers
Rethinking Potato Salad by Susan Russo for NPR



Iris said...

That sounds delicious! I also love making potato salad using hummus as a replacement for mayonnaise. Makes it nice and creamy without making me gag (which the smell of mayonnaise does to me)

Megan said...

That looks so yummy. I miss my summer potato salads but in our family we cannot have gluten, dairy, egg, or soy. There is not a mayo to suit our needs.

Does anyone have a potato salad recipe that meets those requirements?

Malcolm said...

Megan, there are several "flavors" of Veganaise. The one we use is grape-seed oil based, and has no eggs, gluten, dairy, or soy. Does have a bit of mustard flour, and a couple other spices. Fits your definition, and ours. We use lots of it! Also works well for macaroni salad using brown rice noodles.


Rach said...

Once again Karina, I love your writing as much as I love your recipes :)

Karina Allrich said...

Iris- Great idea- to use hummus.

Megan- I have several non-mayo, egg-free, soy-free potato salad recipes here on the blog. Just click on the Labels: link above (right below the post) that says: potato salad. That link will bring up all my potato salad recipes.

Malcom- Thanks for sharing that detail- that's the Veganaise I use.

Rach- Aw. Thanks, Babycakes.

xox Karina

lorrwill said...

Hey! How do you know that I have a talking to kittens voice? LOL

Great recipe as usual.

Stephanie said...

Hi Karina. I was wondering if you ever try using chia seeds as an egg substitute? I am looking for one and saw this online and was curious.


Karina Allrich said...

lorrwill:: :-) xox

Stephanie- I have not tried chia seeds. They are so tiny- like poppyseeds. I haven't had much luck trying to use seed gels. I thicken with a little tahini or raw agave. xox


Boabe de Cafea said...

Mmm...very tasty, I'm sure!

The InTolerant Chef said...

I think you think about potatoes a wee bit too much honey. Perhaps you should try a low carb/starch diet. I bet you wouldn't let a little thing like a scarlet letter keep you away from your spuds!

Kalyn said...

Oh that looks so delicious! I miss potatoes, sigh (although of course I do eat them once in a while, because I'm not into denying myself things!)

And I am seriously coveting that green fork!

Karina Allrich said...

Boabe de Cafea- Yep.

Intolerant Chef- I love me my spuds. And they love me back. Even when I sport my tongue firmly in my cheek. ;-)

Kalyn- I found this fork at World Market. Do you have one in SLC?

xox Karina

Sally Parrott Ashbrook said...

Wait--there's a soy-free Vegenaise? I thought they all had soy protein isolate in them. What is the soy-free kind?

Karina Allrich said...

Sally- I just looked at my grapeseed based Veganaise- it has soy protein listed (aka MSG). No soybean oil. If you react to MSG then I'd avoid soy protein isolate, etc (hydrolyzed vegetable protein is another moniker for MSG). Bummer, huh? Karina

מתכונים said...

i like this Recipe

Nancy @ TheSensitivePantry said...

Karina - Love the potato salad. Is it bad that I want to eat the photos as much as the salad? They're amazingly yummy.

Natasha said...

Wow, this is fabulous. Potato salad without the guilt. Healthy ingredients :)

Laurie Ann said...

Karina, I'm from Idaho, the spud capital of the world...can't wait to try this recipe. I like the simplicity.

Sherri said...

This sounds great. I will use a simple oilive oil instead of the mayo. It is light, simple and delicious.

Dave said...

My dear wife picked up a a bunch of these potatoes at the farmer's market and we've been loving them. Have to give you salad recipe a try. Thanks!

Cathy said...

I am in awe of the photo. It is quite beautiful, oh and I can't wait to make the potato salad too.

Gluten-Free Goddess eBook on iTunes