No Potato Salad

Overall Rating
Your RatingYou must log in

Get started right now with our FREE Paleo Starter Kit:

Inside, you’ll discover...
  • 25 Delicious Paleo “Starter” Recipes
  • Our complete “Paleo Food Swaps” guide
  • A complete starter shopping list
  • Tons more free resources

No Potato Salad

Servings 4

Total Time: 20 minutes

Cook Time: 20 minutes

Nutrition Information

calories 145

carbohydrate 11g

protein 6g

fat 10g


  • 1 head(s) cauliflower chopped into small florets
  • 2 medium celery stalk(s) diced
  • 1/4 medium onion(s), yellow finely diced
  • 1 tablespoon(s) parsley, fresh finely chopped
  • 2 large egg(s) hard boiled, shelled, and diced
  • 2 tablespoon(s) Paleo mayonnaise
  • 1 tablespoon(s) mustard, dijon
  • 1/2 teaspoon(s) sea salt (optional)


  1. Add 1 inch of water to the bottom of a medium pot (with lid). Insert steamer basket and fill with chopped cauliflower. Cover.
  2. Steam cauliflower on the stove top over medium-high heat until slightly tender, about 10 minutes after water begins to simmer (overcooking will develop a stronger "cauliflower" smell, and a mushy texture).
  3. Drain cauliflower and rinse with cold water to cool immediately. Place in a large bowl
  4. Add celery, onion, parsley, and egg.
  5. Stir in mayonnaise, dijon mustard, and sea salt (if desired).
  6. Serve immediately or store in refrigerator.

This recipe inspired in part or in whole from here


  1. Doesn’t Vegenaise have soy in it? I cannot eat soy, and that makes it non-Paleo — if there are any non-soy vegan mayonnaise substitutes, I’d be very interested in purchasing.

  2. I love it! It is so good I almost cannot stop eating it. I use grape seed oil (no soy) instead of veganaisse and it is wonderful. I never knew cauliflower could be so great.

  3. I made this last night and it was SO GOOD. I used dill instead of parsley, and added a few capers (borderline paleo, I guess, but I like them once in awhile.) It was seriously amazing. I would even say I liked it better than regular potato salad — the cauliflower gave it a nicer, less mushy, texture. Thanks for the great recipe!

  4. I’m new at this so was wondering would I eat this as a meal in itself or as a side?? Or I’m guessing it could be both?? Am kind of struggling with the whole portion size of everything :)

    1. Hi Claire,

      You’d have this as a side to a larger entree. It’s only 6 grams of protein and about 150 calories, so unless you used this recipe and ate 2 servings, it wouldn’t really be a meal. All of our recipes tell you how many servings they provide, so go off of that. If it’s a “side”, then know that with one serving you should be able to have something more substantial on your plate. Alternatively you could always add some chicken or other meat to this salad and make it more of a meal. Hope that helps.

  5. You can make your own mayo. Just put 2 egg yokes and the juice of a lemon in a food processor and slowly pour in 1 cup of olive oil while it is running.. BAM mayo.


  6. I use Hain’s Safflower Mayonnaise. It’s pretty good; although, nothing to me is as good as Best Food’s Mayonnaise (but soy).

  7. This is truly delicious. I used dill weed as well. (OUT OF PARSLEY) I also dont care for boiled eggs so didnt add to 1/2 the batch. Thank you for this recipe. LOVE A NEW twist on an old recipe.

  8. I make my own mayonaise out of avocado oil and whole eggs, apple cider vinegar, raw honey,dijon mustard and sea salt.

Leave a Reply