Discover the best creamy Cajun Potato Salad with fork-tender potatoes, zesty Creole mustard, and bold Cajun seasonings. Perfect for any BBQ or potluck! This is my favorite way to make potato salad. Great with gumbo!
We’re making a big batch of the best classic potato salad today in the Chili Pepper Madness kitchen, but this isn’t your typical potato salad recipe.
Like many, I grew up eating potato salad at holidays, picnics, and backyard BBQs. It’s a creamy, tangy side dish that goes with just about anything. But honestly? Most potato salad recipes always felt a little bland to me.
This version is different. It’s my best potato salad recipe, a bold, flavorful Cajun potato salad kicked up with plenty of spices and Creole mustard for a zesty twist you won’t find in ordinary recipes.
It’s perfect for any cookout, but I especially love it with a big bowl of gumbo. Down in southern Louisiana, you’ll even find people serving potato salad right in their gumbo - highly recommended!
Whenever you serve it, I think you’re going to love this spiced-up version.
Let’s talk about how to make potato salad that’s actually bursting with flavor.
Cajun Potato Salad Ingredients
- Potatoes. I am using red potatoes for this recipe, but you can use yellow potatoes, like Yukon gold or other waxy potatoes, or white potatoes.
- Bell Pepper. Use jalapeno for a spicier version.
- Celery.
- Green Onion.
- Parsley.
- Mayonnaise. I use either Duke's mayo or make my own homemade mayo, but you can use your favorite brand.
- Creole Mustard. Whole grain mustard is a good substitute. Classic potato salad uses yellow mustard or Dijon mustard, which are fine here, but a good Creole mustard will add more zestiness.
- Seasonings. Cayenne, paprika, and salt and pepper. Or, use Cajun seasonings. Onion powder is a nice add.
- Hard Boiled Eggs.
How to Make Potato Salad - Step by Step
1. Boil the Potatoes
Add cubed potatoes to a large pot and cover with cold water. Season the water generously with salt. This helps season the potatoes from the inside out.
Bring to a boil and cook for about 10 minutes, or until fork tender but still holding their shape.
Tip: If your potato chunks are larger, you may need 12-15 minutes. Start checking at 10 minutes to avoid mushy potatoes.
Drain and let them cool slightly until easy to handle.
2. Make the Creamy Dressing
In a large mixing bowl, combine chopped bell pepper, celery, green onion, parsley, mayonnaise, Creole mustard (or your favorite mustard), and your Cajun seasonings.
3. Mix the Dressing
Stir everything together until smooth and creamy. This is your flavor-packed dressing. Taste it now and adjust the seasoning if needed.
4. Add the Potatoes
Gently fold in the cooked potatoes, making sure each piece gets coated in that creamy, zesty dressing.
5. Stir in the Eggs
Add in chopped hard-boiled eggs and stir again.
Texture Tip: Prefer a chunkier potato salad? Stir gently and leave the potatoes more intact. Like it creamier? Give it a bit more mashing action.
6. Final Taste and Adjust
Give it a final taste. Add more salt, Cajun seasoning, or an extra spoonful of mayo or mustard if you want it even creamier or bolder.
7. Serve and Enjoy
Serve right away or cover and refrigerate until chilled. It's great either way!
Serving Idea: In Louisiana, you’ll often find potato salad served right in a bowl of gumbo, and it’s fantastic.
Boom! Done! This Cajun potato salad is creamy, zesty, and packed with flavor. No boring bites here. How are you serving yours?
Best Ways to Serve Potato Salad
Potato salad is the perfect side dish for fried chicken, fried seafood, or anything hot and crispy. In parts of Louisiana, it’s also famously served with gumbo! See below.
It’s also a must for backyard barbecues and anything off the grill. Just make a big bowl of creamy, flavor-packed potato salad, and let your guests dive in. It’s always a crowd-pleaser.
Is Potato Salad Served with Gumbo?
Absolutely! In southern Louisiana, it’s common to serve potato salad alongside gumbo, and some folks even scoop it right into the bowl. The creamy, tangy potatoes are perfect for soaking up rich, spicy broth. Give it a try next time you make gumbo!
Try it with my Cajun Chicken and Sausage Gumbo recipe.
Recipe Tips & Notes
Should I Peel the Potatoes for Potato Salad?
Peeling is optional! I like my potato salad with the skins on. They add great texture and a bit of extra nutrition. But if you prefer a smoother bite, feel free to peel them.
Optional Additions
This recipe is easy to customize. Popular additions include red onion, dill pickles, sweet pickles, relish, or a splash of vinegar for extra tang. Make it your own!
Crunch Factor
The raw peppers and celery add a nice crunch to every bite. If you prefer a softer texture, you can quickly sauté them in a bit of oil to mellow out the crunch before mixing them in.
Creamy or Chunky Potato Salad?
I like a chunky potato salad, so I stir the potatoes in gently to keep them mostly whole.
But if you love it creamy, mash the potatoes a bit as you mix, almost like creamy mashed potato salad, which is also delicious.
Sometimes I go for a mix of both - chunky and creamy. It’s totally up to you!
Storage & Leftovers
Store any leftover potato salad in a sealed container in the refrigerator for up to 5 days. It’s delicious served cold, but you can also enjoy it gently warmed in the microwave or oven if you prefer.
That's it, my friends. I hope you enjoy my Cajun style potato salad recipe. Let me know if you make it. I'd love to hear how it turned out for you. Keep it spicy!
Great Gumbo Recipes
Serve your spicy potato salad with some of these awesome gumbos:
Want More Potato Recipes?
If you're like me and can't get enough potatoes, try some of these recipes:
- Scalloped Potatoes
- Papas Arrugadas
- Papa a la Huancaina (Peruvian Potatoes)
- Jalapeno Popper Twice Baked Potatoes
- Papas con Chile
- Papas con Chorizo
- Bombay Potatoes
- Smothered Green Beans & Potatoes. Southern-style smothered with smoky bacon and Cajun spices.
Got any questions? Ask away! I’m happy to help. If you enjoy this recipe, I hope you’ll leave a comment with some STARS. Also, please share it on social media. Don’t forget to tag us at #ChiliPepperMadness. I’ll be sure to share! Thanks! — Mike H.
The Best Classic Cajun Potato Salad Recipe
Ingredients
- 2 pounds red potatoes scrubbed and cut into 1-inch pieces (You can use yellow potatoes instead - peeled, if desired, or leave unpeeled)
- 1/2 bell pepper diced (or use a jalapeno)
- 1 stalk celery diced
- 1 tablespoon chopped green onion
- 1 tablespoon chopped parsley
- 3/4 cup mayonnaise
- 1/4 cup Creole mustard or use whole grain - or more to taste
- 2 teaspoons cayenne pepper
- 1 teaspoon paprika
- Salt and black pepper to taste
- 6 hard boiled eggs chopped
Instructions
- Add the cubed potatoes to a pot and cover with water. Add a bit of salt and bring to a boil. Boil for 10 minutes, or until fork tender. Drain and cool slightly.
- To a large bowl, add the bell pepper, celery, green onion, parsley, mayo, mustard, and seasonings. Stir to combine.
- Stir in the cooked potatoes to completely coat them in the creamy mixture.
- Gently stir in the chopped hard boiled eggs. Mix or mash the potato salad to your preferred consistency. Do you want it chunky? Creamy? Both?
- Taste and adjust for salt.
- Serve, or cover and refrigerate to serve chilled.
Video
Nutrition Information
NOTE: This recipe was updated on 7/22/25 to include new information and video. It was originally published on 4/13/22.
Jim says
Mike, this is absolutely the very best potato salad i have ever devoured! I did , however, add one other ingredient. And that was crumbled bacon! This is the only potato salad i will ever assemble!
Mike H. says
Super happy to hear it, Jim - enjoy!
William says
Love this recipe. Every time we boil crawfish we save a few pounds of the potatoes just for potato salad the next day. So very spicy!! Enjoy your recipes.
Mike H. says
Absolutely glad to hear it, William. Thanks!
Denise Williams says
Oh, Mike. It all looked delicious until I saw all the mayo. I am not a mayo girl at all!! Wonder what could be substituted other than sour cream or yogurt?
Mike Hultquist says
Hard to sub the mayo and get the same flavor, Denise. You need that "creamy" factor. One idea is whipped avocado. I love the combo of potatoes and avocado. Hummus could even work. Not sure if you have a favorite mayo alternative. Happy to discuss.