Food, Recipes, Vegetables

Everyday Paleo "No Potato" Salad

As mentioned on my Facebook page, we have been busy all weekend celebrating my dad’s 70th birthday!  My sister, brother-in-law, and my sweet little niece came to visit along with my brother and of course my dad and his wonderful wife Sandy.  This weekend was dedicated to my dad and filled with precious moments spent with my family.  We all did a lot of laughing, a little bit of crying, and a whole bunch of hugging and I slept soundly at night with a house filled with the ones that make my little corner of the universe bright. I am grateful to have a family that I hold so dear to my heart and trust me; I know how lucky I am.

At family gatherings I often think about how my mom would have made the occasion special with her laughter, playful spirit, and her uncanny ability to magically clean up any and all messes when no one else was looking.  So yes, I miss my mom’s presence at these events but missing her makes me appreciate the love she gave to us and that love continues to hold our family together.

For my dad’s celebration we ate a ton of food and played in the creek with the kids, which included my dad falling in the water fully clothed while playing “creek” volleyball.  He was not hurt a bit and it was actually the highlight of the weekend to see my healthy and active 70 year old father jumping up dripping wet from the creek bed and laughing jovially at his funny predicament.

Now on to the food!  Amongst grilled sausages, cabbage salad, watermelon, carne asada, and guacamole, I made a “No Potato” Salad following from memory my mom’s potato salad recipe. I made a paleo version using my homemade mayo with a twist, and cauliflower in place of the potatoes.  The result was out of this world delicious and satisfied my longing for the creamy comforting salad that used to be a staple at family gatherings. Everyone at the party gave the salad two big thumbs up!  I apologize for the lack of exact measurements in the recipe, but sometimes when food comes from the heart it simply happens, and I think when you make this dish, it will happen just fine for you as well.  I hope you enjoy!

"No Potato" Salad

Everyday Paleo “No Potato” Salad

2 heads of cauliflower

1 dozen eggs, hard-boiled and diced

1/2 a medium sized red onion, finely diced

6-8 celery stalks, finely diced

A lot of dill pickles, diced

About 1 1/2 cups of my Paleo Mayo with 2 tablespoons of dried dill and 1 teaspoon of crushed garlic added.

About 1 teaspoon of yellow mustard

Black pepper to taste

Cut the cauliflower into large florets.  I used my pressure cooker to cook the cauliflower by placing the florets in the cooker, filling the cooker with about 4 inches of water, locking the lid, bringing to pressure and cooking for about 2 1/2 minutes.  Remove from heat immediately and run the cooker under cold water to quickly bring down the pressure.  Remove the lid and pour the cauliflower through a strainer and rinse with cold water to stop the cooking process.  You want the cauliflower to be soft but not mushy!  If you do not have a pressure cooker, steam the cauliflower around 7-10 minutes, cooking until tender but not mushy.  Rinse the steamed cauliflower under cold water to stop the cooking process.  Drain the cauliflower well and pat dry with paper towels.  Crumble the cauliflower into a large mixing bowl, add all of the remaining ingredients including the mayo, mustard, and pepper and mix well.  Either eat right away or let chill for a couple of hours before serving.  This salad was HUGE and could serve at least 15 people so cut the ingredients in half unless you are feeding a crowd or want a lot of leftovers.

As always, Enjoy!!

[nggallery id=162]


Sarah Fragoso

Sarah Fragoso is an international best selling author of 6 books, co-owner of the Chico, CA based gym JS Strength and Conditioning, and founder of the Everyday Paleo franchise. Sarah is the co-host of the popular Sarah and Dr. Brooke Show podcast and she also conducts workshops and retreats on the subjects of nutrition, lifestyle and fitness.

Her message is from the heart and she carries a genuine desire to help other families looking for guidance. These attributes have contributed to her successes and provide the drive to keep the discoveries coming.

You may also like...


  1. Jenni S says:

    Sounds great… can’t wait to try it! Thanks!

  2. John says:

    This salad rocked! I will never miss “potato” salad again.

    1. Sarah says:

      Your grilling rocked!! Thanks for being amazing as always.

  3. Colleen says:

    O my! Yummm!

  4. Michael says:

    You did it again Sarah. Made it tonight. Tastes like the potato salad but better! Please know that I and probably many others truly appreciate your great recipes and kind words about your family. I’m turning 50 this year and hope to be as spry as your Dad.

    1. Sarah says:

      Thank you so much Michael, so glad you liked the salad!

  5. Laura says:

    Awesome, awesome, awesome!!!

    1. Sarah says:

      Thank you Laura!!

  6. Yesenia says:

    that cabbage salad looks yummy. whats in it?

    1. Sarah says:

      The cabbage slaw is super simple, just shredded green and purple cabbage, diced apple, diced cucumber and I made a vinaigrette with olive oil, balsamic vinegar, dried thyme, pepper, and a little sea salt.

  7. sally wimberley says:

    I MUST SAY– the timing is perfect –gonna make this today! and also–YOUR DAD!
    I am 53 and fee3ling mighty fine– but your Dad is a sure sign to me– that 70 is the new 50! O M Heavens! rock on

    1. Sarah says:

      I agree! My Dad is living life to the fullest – a great example for us all!

  8. sarena says:

    Let the good times roll!! Salad sounds great. I tried a new paleo mayo recipe this past weekend and really enjoyed it. It used half coconut oil and half EVOO! I used powdered mustard too as I am concerned with the vinegar in “wet” mustard and how I react to it.

    1. Sarah says:

      I want to try mayo with coconut oil too, it sounds really good! Thanks Sarena!

  9. Sue says:

    Hi Sarah, recipe looks lovely and will try tonight. Thank you for sharing you thoughts and feeling re your mum. I lost my mum 4 years ago and feel the same at family gatherings, it was comforting to read your feelings on it.

    I went off and looked at your sisters site and have pre-ordered her childrens piano course. We homeschool in the UK and this will come in very handy. Her music is just beautiful :0) Thank you Sue

    1. Sarah says:

      Thank you so much Sue! My sister is an amazing musician and teacher, I hope you enjoy her piano course! You’ll have to let me know how it goes. : )

      1. Tiffany says:

        How would I go about finding your sisters piano course? I’ve been meaning to get some piano books forever but I just haven’t yet. I would love to check out hers to see if they would work for our family. Thanks!

        1. Sarah says:

          Hi Tiffany! You can find my sister piano course here.
          She is an amazing musician so check our her music while you are on her site!

  10. Interesting! We rarely buy cauliflower here but we always have broccoli… I wonder how that would look?!

    1. Sarah says:

      It would look like green potato salad! LOL!!

    2. I looking for a really good low carb Broccoli Soup. Any takers? Thanks in advance!!

  11. Sujata says:

    Cauliflower soup is something I’ve done but this looks like a new & exciting way to prepare cauliflower – will definitely check it out. I also came across a great simple salad at Whole Foods last month. Lemony Avocado Slaw- really easy to prepare and yummy. Here’s the link:

    1. Sarah says:

      Yum Sujata, the slaw sounds amazing!

  12. Tracy says:

    If you don’t look too closely this even looks like my father in laws potato salad!! He is southern and I can tell you in the south they are serious about potato salad!!! I am definitely trying this recipe though!

  13. Joanne says:

    I have been making this recipe for my family for the past few months and it has been a hit every time! I have even made it for my dad, who is a total potato-aholic even since I can remember, and to my surprise he also LOVES it! I have been searching for things to help him detox from this ridiculous habit of a potato with every meal, so this was a great step to take one more thing to the potato free zone for him. Thanks Sarah!

  14. Suzanne says:

    Sounds delicious! I have made your purple cabbage salad with the mango and LOVE it! I was looking for something to bring camping in place of potato salad and this will be perfect! 🙂

  15. Nicole says:

    Thank you so much for sharing this recipe! It looks delicious and I can’t wait to try it! I bought your cookbook last week and have loved every recipe I’ve tried. I have been trying to eat paleo for some time but was finding it so hard to think of new things to make- so your cook book has been a huge help. I work as a dietitian and have been sharing your recipes with patients and encouraging them to make the purchase as well. I also started using the workout plans provided… love it all! Thank you!!!!!!!!! You’re an inspiration!

    1. Sarah says:

      Thank you so much NIcole, so glad you are enjoying the book and thank you for referring me to your clients!

  16. Sandy says:

    You’re brilliant!

    1. Sarah says:

      Thank you!!! : )

  17. This looks amazing. Definitely trying this one out over the weekend.

  18. Erin says:

    I’m so excited to try this salad. We are a ‘tater salad lov’in crew. Thank you for laying the recipe out for both a large group or a small one.

    1. Sarah says:

      You are very welcome Erin, and I hope you enjoy it as much as we did! In fact, I can’t wait to make it again… : )

  19. Ashley says:

    Hi! Would you mind telling me what brand of Sausages or hot dogs those are? I can’t find paleo friendly hot dogs or sausages anywhere. Also do you know of a good deli meat brand? Thanks. We are gonna make this salad this weekend. :0)

    1. Sarah says:

      The sausages and hotdogs are from Applegate Farms, and they also make a decent deli meat. I also love US Wellness Meats!

  20. Tom says:

    This stuff was great. I added a bit of bacon, well because everything tastes better with bacon, no actually my mom always adds it to her potato salad. Outstanding recipe, cauliflower is so versatile, I have been using it as a sub for fried rice now I have another wonderful use for it. Thank you Sarah!

    1. Sarah says:

      GREAT idea to add bacon, I’m doing that next time for sure!

  21. Jen Sanchez says:

    This has all the flavors of my mom’s macaroni salad except sliced black olives. I added those and it’s a big bite of memories without the blood sugar spike and guilt!
    When I gave him a taste-test before dinner, my non-paleo-believing husband said “I think we’re actually going to like this!” Great salad Sarah!

    1. Sarah says:

      I love it Jen, so cool!

  22. Hey there! I tried this recipe and made a video of the process. We used Miracle Whip instead though… it was DELICIOUS!!!!

  23. YAY!!!!!!! LOVED THIS!!!! So happy! I feel like I can serve this to guests, and no one will miss the potatoes. I love hosting parties, and it is always a challenge to feel like non-paleo guests will be satisfied! This was awesome! Thanks again!!!!

  24. Diana says:

    This would also be amazing with kohlrabi!

  25. Samantha says:

    I have to tell you… I made this weekend for a bbq we had. I did not tell peopel it was cauliflower salad instead of potato salad. And they loved it! but my friend did tell me that if i would have told her it was cauliflower instead of potato… she would not have tried it. And that people, is why i am sneaky 🙂
    thanks for the great recipe!

  26. Tiana says:

    Absolutely Amazing! Just finished making it. Added in bacon. I found a recipe for baconnaise and may try that next time. Thanks for the awesome recipe

  27. Rachel says:

    Just made this! Yummo! Keep the delicious recipes coming Sarah! 🙂

    1. Sarah says:

      You got it girlfriend! I want to come see you so we can cook together, you are such a wizard in the kitchen. Miss you! Hugs to all your boys. : )

    2. Sarah says:

      John just said, “so that’s how Chris got his muscle up!” Um yea, I’ll totally take credit for it. LOL!!

  28. Jen D. says:

    I made this salad this weekend and added a little extra egg and green olives. I sure hope green olives are Paleo. Ate it for breakfast the past 2 days and can’t wait for it again tomorrow. So weird how my cravings have changed – who would have thought I’d be eating cauliflower for breakfast!

    I also gave up my morning Diet Coke and switched to coffee with coconut and a little vanilla extract. I bought 3 cans at Trader Joesvand afterwards read a post that said it should be full. Why isn’t the light version OK? I like the taste better than the full fat brand I bought earlier.

  29. debbie seward says:

    The husband hates potato salad….two helping later, he likes this! Hit!!!! Home-run!!!
    thanks for the recipe, because I love potato salad and it is such a nice thing to be able to bring to summer events

  30. Love this “no potato” potato salad. Made it for a big cookout with friends, even though I am the only cavegirl amongst the bunch, everyone loved it! I even added bacon for a little extra kick. Yummmmmm! Can’t wait to make it again. 🙂

  31. Beth Birdsell says:

    Love the “no Potato Salad” I threw in some steamed brocoli and home made MAYO love it. Thank you for the share Sarah…

    1. Sarah says:

      You are very welcome and thank you!!

  32. Finally tried it! I LOVE THIS.

  33. Sharon K. Smith says:

    Mmm, mmmm, good! This is phenomenal. Thanks for the recipe!

  34. Jason Betancourt says:

    I was nervous about the mayo, but it came out well. Everyone loved it. When you say a lot of pickles you mean a lot. I added olives and it was just as well.

    1. Sarah says:

      Glad it worked out for you!!

  35. Hey Sarah, I know this post was from July, but I’m hoping you are still reading it anyway. Do you have any suggestions for what I could substitute for cauliflower? I know you use it in quite a few dishes, but I hate cauliflower. I don’t mean dislike, I mean hate! As in, if Cauliflower were the last food on earth, I’d rather starve to death than eat it, kind of hate. Turnips? Rutabaga? which both seem too sweet for a savory dish like this, as do yams or sweet potatoes. Ideas?

    Thanks in advance, Sarah. And thanks for your great site.

    1. Sarah says:

      How about cabbage or broccoli??

      1. I read where Broccoli would be great as well, just a more greener appearance. I omitted the Mustard from my first batch, put a little in a separate dish. Both are great! We’re of German descent so mustard is the norm.

    2. Be careful as Sweet Potatoes is high in carbs.

  36. Marcia says:

    Hi Sarah,

    So excited to make this and the homemade mayo … possibly tomorrow. Ever considered adding bacon?

    So thankful for your website! 🙂

  37. Lori says:

    You probably won’t see this… but thougt I would post it just the same. I am new to paleo and it’s interesting some of the best recipes come from me not prereading the recipe beofore I start assembling it… I cut the cauliflower into thin slices (uncooked), sliced a sweet yellow onion (didn’t have red), added the rest of the ingredients except mayo and mustard. As I was mixing the sauce, I got a little carried away, 1 Tbs instead of 1 tsp of mustard. It was then that I realized I was supposed to cook the cauliflower… Oh well too late now. I let my salad sit in fridge for a couple of hours to let the flavors develop. Mmmm was it good. It would be great with crumbled bacon…. I think I’ll cook it up right now and add it to my recipe.

    1. Sarah says:

      Wow, I love it! Sounds awesome and I’ll have to try it this way, and yes, you’re right, sometimes the best meals happen by accident. LOL!

  38. this looks amazing and perfect for the summer, might have to bring this up to the cottage soon!

  39. Thanks for the recipe. However upon completing the salad I realized there was one thing missing that no paleo recipe should be without.

    I added 6 slices of finely chopped Organic, uncured Bacon and then it truly was Amazing.

    1. Boy, that does sound yummy, think I’ll give it a try.
      Do you know of a substitute for rice? Been using brown rice but not sure that is a good thing.
      Thanks for any info you may have!

  40. Tami says:

    Just made this last night and I think it’s even better tonight. I changed the recipe a little to be more like my potato salad. I used a few sweet pickles instead of the dill and added some sliced olives. Everyone loved it. I think I’ve found a new favorite!

  41. DeNelle Knutzen says:

    Question: When you say a lot of pickles, any idea kind of a guesstimate?

  42. Our family has made a commitment to a Low Carb diet. I’ve been searching the web for Low Carb recipes that would replace potatoes, pasta and bread, when I found your “no potato salad”. Made it the first time for lunch today. Gave my husband a taste with his eyes closed, he immediately said it was Potato Salad! If you can fool a guy then you’re on the right track. Thanks!

  43. tony says:

    Do your books offer all nutritional facts for each recipe ? I need to eliminate more than just carbs/sugar ?

    1. No, I’m sorry, the books do not offer the nutritional break down for each recipe but you can always use something like FitDay to figure out the nutritional analysis.

  44. Ashley says:

    What are the macros for this recipe? Carbs, fat, and protein?

  45. Alissa says:

    I love this recipe ! Just wish I know the nutritional facts like calories and carb !

  46. dawn says:

    where the heck is the print button?!

  47. Karen Equils says:

    Please add print recipe button!!! Every frigging reply printed out with recipe!

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.