Cauliflower Fauxtato Salad – Tastes Like the Real Thing!

This post may contain affiliate links from which I will earn a commission. Learn more in our disclosure.

Do you love potato salad but want a low-carb alternative? Here is a fabulous recipe for cauliflower potato salad that is guaranteed to please and has even been known to fool some potato salad lovers into thinking it’s the real deal!

Cauliflower Potato Salad

I’m so excited to share my Low-Carb Cauliflower Potato Salad recipe (aka Faux Tato Salad) with you today. This one has been on repeat in our house recently, and neither my husband nor I can get enough of the refreshing flavor of the delicious, soft cauliflower coated in the creamy cashew sauce.

It’s been our new favorite side dish.

Growing up in a Korean household with mostly home cooked Korean dishes, potato salads were always a special treat for me that I would only get a chance to enjoy at school outings and picnics. I absolutely loved the taste and texture, and the slight vinegary flavor complemented the cooked pillowy potatoes so so well.

Nummmmm….

After enjoying the heck out of them all throughout college at the campus cafeteria, I actually forgot about them and haven’t had them much for the past several years. I’ve also been eating more low carb recently because of my candida issues, which flare up with too much sugar or too many carbs, so it wasn’t something that I would normally make…

…until this cauliflower potato salad recipe came along.

Want to Save This Post?

Enter your email & I'll send it straight to your inbox. Plus, you'll get healthy living updates too.

Save Recipe

Cauliflower Potato Salad?

This recipe replaces the traditional potato with steamed cauliflower, but this version is even more delicious than the original kind. My husband actually thought this was a real potato salad when he first took a bite, and we got a good laugh about how I fooled him yet again with a delicious and healthy substitution that he couldn’t detect.

Unbelievable!

So cauliflower works as a rice substitute in Grain-Free Sushi, a potato substitute in this Low-Carb Shepherd’s Pie, as a “fauxtato” in these Keto Mashed Potatoes–and now this!

But really… is there anything that cauliflower CANNOT do?

Yeah–maybe there. I mean, I still haven’t seen a Cauliflower Peanut Butter Cup, or a Cauliflower Hershey Kiss…..but I’m not giving up hope yet.

What Makes This Low-Carb Potato Salad Special?
Hint: sauce

What makes this cauliflower potato salad really shine is the cashew cream sauce that’s packed with flavor and pulls the dish together beautifully. I decided to create this yummy sauce instead of using mayonnaise because I’ve had sensitivities to eggs in the past so it’s something I try not to eat them too often.

In this egg free “mayo,” soaked cashews (see how to soak nuts) are blended with yummy ingredients like lemon juice, mustard, and garlic, yielding a smooth and addicting sauce that’ll wake your taste buds as you enjoy this low carb potato salad.

It’s so good that I’m thinking of making a double batch of the sauce for next time just to have it to drizzle over salads (like this Broccoli Jicama Salad) and bowls.

Cauliflower Potato Salad

What to Eat with this Low-Carb Potato Salad

We’ve been enjoying this cauliflower potato salad as a side dish next to roasted chicken or grilled steak, but it’s hearty enough that you can eat it on its own as a main dish. It also keeps well (and actually gets better the longer it sits!) and is portable, so it’s perfect to bring to a picnic or a potluck.

It would also be fantastic included in a packed lunch, or of course at a cookout! Hey hamburgers and hotdogs, those aren’t potatoes in that salad sitting next to you –ha!

And best of all, this low carb potato salad packed with all the healthy good-for-you vegetables so you know you are getting in plenty of nutrients in the most delicious way!

Move over potato-shmato. Cauliflower is where it’s at!

Low Carb Potato Salad

Other Healthy Sides

Though not all of these are keto, the following are great healthy side dishes for your next cookout or gathering any time of year.

Sugar-free Baked Beans–These Maple Baked Beans can be ready literally in less than an hour!

Spaghetti Squash Salad – This recipe is so good, even those who don’t like squash will love it

Moroccan Carrots – A great make ahead side that’s kid friendly too.

Recipe Notes and Substitutions

  • Raw Cashews: You will want to use only raw cashews for this recipe. Roasted will yield a totally different flavor. It might be nice but won’t seem like a typical dressing.
  • Mayonnaise: Of course, if you aren’t avoiding eggs, you can use your favorite mayonnaise as the dressing for this low-carb potato salad.
  • AIP: And if you’re on the AIP (autoimmune paleo) diet, you could sub in this Vegan Avocado Dressing for the sauce. It will taste amazing, but it will be green :).  There are a few AIP ranch dressings you could use as well.
  • Nut-Free Dressing: If you can’t eat nuts, this Vegan Ranch Dressing is a fantastic alternative to the cashew dressing.
  • THM: This recipe fits in as an “S” if you are on the Trim Healthy Mama plan.
cauliflower potato salad in a bowl sprinkled with paprika

Low-Carb Cauliflower Potato Salad

Love Potato Salad but you’ve gone keto? This Cauliflower Potato Salad is the perfect low-carb companion to any meat including cookouts and potlucks!
5 from 5 votes
Print Pin Rate
Course: Salad
Cuisine: AIP, Dairy-Free, Gluten-Free, Grain-Free, Keto, Low-Carb, Paleo, THM:S, Vegan
Keyword: cauliflower potato salad
Prep Time: 10 minutes
Cook Time: 5 minutes
Resting Time: 1 hour
Total Time: 15 minutes
Servings: 4 servings
Calories: 243kcal

Ingredients

  • 1 large head of cauliflower (cut into bite-sized florets)
  • 1 small red onion (diced)
  • 2 stalks celery (chopped)
  • 2 green onions (chopped)
  • 1 teaspoon dried dill
  • 1 teaspoon garlic powder
  • 1/4 teaspoon ground black pepper
  • 1/4-1/2 teaspoon celery salt
  • paprika (for garnish)
  • salt and pepper to taste

Cashew Cream Sauce

Instructions

  • Place a steamer insert into a large saucepan and pour in water to just below the bottom of the steamer
  • Turn the heat to medium high and bring the water to a boil.
  • Bring down the heat to medium low to simmer, then add cauliflower florets, cover, and steam until tender, about 5 minutes.
  • While the cauliflower is steaming, place all ingredients for the cashew cream sauce in a blender, and blend until smooth and creamy. 
  • If the mixture is too thick, add a bit more water and blend again until it reaches the right consistency. Set aside.
  • Place the steamed cauliflower in a large mixing bowl.
  • Add red onion, celery, green onions, dill, garlic powder, sea salt, and ground black pepper. 
  • Pour in the cashew cream sauce over the vegetables and toss together to coat. 
  • Place in refrigerator for 1 hour before serving, so the flavors can meld together.
  • Sprinkle with paprika before serving. 

Notes

  • Raw Cashews: You will want to use only raw cashews for this recipe. Roasted will yield a totally different flavor. It might be nice but won’t seem like a typical dressing.
  • Mayonnaise: Of course, if you aren’t avoiding eggs, you can use your favorite mayonnaise as the dressing for this low-carb potato salad.
  • AIP: And if you’re on the AIP (autoimmune paleo) diet, you could sub in this Vegan Avocado Dressing for the sauce. It will taste amazing, but it will be green :).  There are a few AIP ranch dressings you could use as well.
  • Nut-Free Dressing: If you can’t eat nuts, this Vegan Ranch Dressing is a fantastic alternative to the cashew dressing.
  • THM: This recipe fits in as an “S” if you are on the Trim Healthy Mama plan.

Nutrition

Calories: 243kcal | Carbohydrates: 23g | Protein: 10g | Fat: 15g | Saturated Fat: 3g | Sodium: 837mg | Potassium: 772mg | Fiber: 5g | Sugar: 7g | Vitamin A: 164IU | Vitamin C: 78mg | Calcium: 69mg | Iron: 3mg | Net Carbs: 18g

Nutritional information is provided as a courtesy and is merely an approximation. Optional ingredients are not included and when there is an alternative, the primary ingredient is typically used. We cannot guarantee the accuracy of the nutritional information given for any recipe on this site. Erythritol carbs are not included in carb counts since they have been shown not to impact blood sugar. Net carbs are the total carbs minus fiber.

I think you’ll LOVE this.

What will you serve this Low-Carb Potato Salad with?

Jean Choi - blog owner at What Great Grandma Ate

Jean Choi is a Nutritional Therapy Practitioner, recipe developer, and food photographer at What Great Grandma Ate. She is also a cookbook author of the Korean Paleo Cookbook. She started her blog to share her story of overcoming years of digestive issues and adrenal fatigue, and to help others realize that nutrient-dense allergen-free cooking can be simple, easy, and delicious. Jean believes that the food you love should love you back through healing and nourishment. For more of her real food recipes and SoCal adventures, follow along on her Instagram and Facebook.

Leave a Reply

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

Recipe Rating




 

17 Comments

  1. 5 stars
    Well done! Mine is still warm, and it is already delicious! In addition to a side, I can see as the filling for a sandwich, and as a topping for greens, in addition to replacing standard potato salad. I do plant- based whole foods w/o added oil or sugar, and this tastes wonderful and decadent while being meeting my requirements. I am very confident that people at my work potluck tomorrow will love it!

    1. So great! Thanks for taking the time to comment and I agree with all of your lovely ideas! So many things can be spreads / sandwich fillings that we wouldn’t think of–like hummus or guac! This is our fave hummus in case you’d like to try it later. Thanks again! https://wholenewmom.com/savory-hummus/

  2. Hi! I am making the cauliflower potato salad. Do I need to cool the cauliflower before I add the celery, onions and nut mayo?

      1. 5 stars
        Thank you so much for getting back to me! I really appreciate it! The salad is in the frig. I am waiting to serve it later for dinner but I tasted it and I have to say it is wonderful! I love it! I will definitely make it again and the dressing is so good! I have made other sauces/dressings with raw cashews and this is the best! I am now going to check out your other recipes!! 🙂

        1. Oh that is so great! This recipe was a guest post so I can’t take credit for it but hopefully you will find some other things you will like. If you would like to reach out before trying something else I’m happy to advise. Most of them I would say are really good but some I am revising. More to come soon. I’m backed up and need to get writing again :).

          I will say that the avocado dressing on here is fantastic and we love the Moroccan Vinaigrette as well.

          1. 5 stars
            Thank you again Adrienne! I will let you know if I have any questions and thank you for telling me about the avocado dressing and the Moroccan Vinaigrette! I am a huge fan of avocado’s and vinaigrette’s too!

            1. You are so welcome! Hope they work well for you! I’ll add on the Healthy Chocolate Fruit Dip too :). You’ll find one of your favorites in there as well……

  3. 5 stars
    I have made this salad and I love it. I do use eggs but really you cannot tell your eating cauliflower or eggs. My husband does not like cauliflower or eggs yet when I make this he has seconds & I have to stop him at thirds.

  4. 5 stars
    Oh my goodness, this looks so yummy! I love cauliflower and potato salad so I’m going to have to make this. I recently found out my daughter is allergic to dairy, I just picked up 12 pounds of cashews so your cashew mayo replacement will be easy to make. 🙂

    1. So glad and hope you like it! Our oldest is deathly allergic to dairy and I avoid it b/c I think I have a minor allergy. Hope to see you around again!

  5. This recipe sounds wonderful! My question is, do the cashews need to be raw, roasted, or it doesn’t matter?
    Thank you!