Salads
This Carnegie Deli potato salad recipe delivers the iconic tangy, creamy texture that made it legendary—without a single drop of mayo. The secret lies in a rich cream cheese base blended with tangy mustard and vinegar, creating a dressing that clings to each potato without turning soupy.
I've perfected this version after countless batches, ensuring the perfect balance of crisp celery crowns, finely diced onions, and just the right amount of zing.
The foundation starts with Yukon Gold potatoes, boiled until tender but still holding their shape, then chilled before mixing with the dressing. This step prevents a mushy texture, guaranteeing each bite stays creamy yet firm.
The dressing is where the magic happens—a velvety blend of cream cheese, Dijon mustard, and apple cider vinegar that delivers that signature Carnegie tang without overpowering the potatoes.
What sets this recipe apart is the attention to texture: crisp celery and onions cut through the richness, while optional add-ins like hard-boiled eggs, dill pickles, or crispy bacon bits elevate it to deli-quality. The salad develops deeper flavor as it chills, making it even better the next day.
Serve it at picnics, barbecues, or family gatherings—it's the kind of dish that disappears faster than you can say "pass the potato salad."
For presentation, garnish with extra celery leaves and a sprinkle of paprika for color and a final touch of sophistication. This isn't just potato salad—it's a celebration of classic deli flavors, reimagined with modern precision. Let's get started on creating the perfect bowl.
Ingredients for carnegie deli potato salad
Classic deli flavors with a creamy, tangy twist—no mayo needed here.
| Ingredient | Amount | Notes |
|---|---|---|
| Yukon Gold Potatoes 🥔 | 2 ½ lb | Medium size, boiled until tender |
| Full-Fat Cream Cheese 🧀 | 8 oz | Room temperature for blending |
| Dijon Mustard 🌶️ | 2 tbsp | High-quality for tangy flavor |
| Yellow Onion 🧅 | 1 whole | Finely diced, crisp texture |
| Celery Stalks 🧅 | 4 whole | Trimmed, cut into crowns |
| Apple Cider Vinegar 🍎 | 1 tbsp | For authentic tang |
| Granulated Sugar 🍚 | 1 tsp | Balances acidity |
| Salt 🧂 | 1 tsp | Kosher or sea salt |
| Black Pepper 🌶️ | ½ tsp | Freshly ground preferred |
| Fresh Dill 🌿 | 2 tbsp | Chopped, optional garnish |
| Sweet Paprika 🌶️ | ½ tsp | For garnish and color |
| Hard-Boiled Eggs 🥚 | 4 whole | Optional, chopped for texture |
| Dill Pickles 🥒 | ½ cup | Chopped, optional tangy bite |
The Yukon Gold potatoes are non-negotiable for texture—medium size holds its shape better than small reds. Whole Foods or Trader Joe's usually carry them year-round, but check the organic section if you want extra flavor. The cream cheese needs to be full-fat—low-fat versions get grainy. For the celery, look for crisp stalks with bright green leaves; Costco sells them pre-washed in bundles, which saves time. The Dijon mustard should be 100% mustard seed—none of that watered-down stuff that tastes like vinegar.
No Dijon? Yellow mustard plus a pinch of turmeric works in a pinch, though it won't be as refined. Fresh dill is ideal, but dried dill at half the amount gets you close if you're in a bind. The apple cider vinegar adds that signature tang—Bragg or Texas Pete are my go-tos, but any good-quality brand works. For the optional add-ins, hard-boiled eggs from the deli counter save time, and Trader Joe's pickles are perfect for chopping. The paprika? Smoked paprika adds depth, but sweet is traditional for that classic deli look.
Potatoes should be chilled before mixing to prevent mushiness—store them in ice water for 10 minutes after boiling. The finished salad keeps 4-5 days in the fridge, though flavor peaks after 24 hours as everything melds. Portion into containers with the dressing on top to keep it creamy. For make-ahead picnics, this is your secret weapon—pack it in a cooler with ice packs and it'll stay perfect for hours.
Why You'll Love This Recipe
- No Chopping Chaos: I swear by this—just dice the onions and celery once, then let the creamy mustard dressing do the work. The Yukon Golds stay intact, so you’re not mashing or overworking them. (Yes, even on a Tuesday night.)
- Deli-Style Magic: That full-fat cream cheese and Dijon combo? It’s the secret. Sweet, tangy, and rich without being heavy—plus, the onions caramelize just enough when tossed in. Honestly, it tastes like the salad I’d order at Carnegie Deli, but better.
- Weeknight & Picnic Hero: Make a big batch on Sunday, and you’ve got lunch for the week. Or pack it in a jar for potlucks—it holds up beautifully. My kids ask for it at school events, and honestly, that’s the best compliment.
- Leftovers That Don’t Suck: Unlike most potato salads, this one tastes even better the next day. The flavors meld, and the cream cheese keeps it luscious. I’ll be real: I’ve reheated it three times, and it’s still my go-to. Budget-friendly? Absolutely.
Step-by-step instructions for Carnegie deli potato salad
This classic Carnegie Deli-inspired potato salad delivers crisp celery crowns and a creamy, tangy dressing without mayo.
Boil and Cool the Yukon Gold Potatoes
Place the 2.5 lb Yukon Gold Potatoes in a large pot and cover with cold water. Add 1 tsp Salt and bring to a boil over high heat. Once boiling, reduce to medium heat and cook for 15-20 minutes until a knife slides in easily with no resistance.
Drain the potatoes immediately and transfer them to a large mixing bowl. Let them cool for 10 minutes before handling. The residual heat helps prevent breaking when you cut them. I find this cooling step essential—it makes the final texture much creamier rather than gummy.
Prepare the Celery Crowns and Onion
Trim the ends from the 4 whole Celery Stalks and cut each stalk into ¼-inch thick slices, keeping them whole (this creates the signature "crowns"). Finely dice the 1 whole Yellow Onion using a sharp knife—you want tiny pieces that will blend seamlessly into the salad.
Add both the celery crowns and diced onion to the warm potatoes. Toss gently to distribute and let them cool completely to room temperature. The celery should remain crisp, so avoid over-mixing at this stage. This prep ensures the celery stays crunchy rather than soggy in the final salad.
Create the Cream Cheese Dressing
In a separate bowl, beat the 8 oz Full-Fat Cream Cheese until completely smooth—no lumps allowed. Add the 2 tbsp Dijon Mustard, 1 tbsp Apple Cider Vinegar, 1 tsp Granulated Sugar, 0.5 tsp Black Pepper, and 2 tbsp Fresh Dill. Mix until fully combined and creamy.
Here's the thing—cream cheese can be tricky. I like to use a hand mixer for this step to ensure it's perfectly smooth. The vinegar and sugar balance the richness of the cream cheese, while the Dijon mustard adds that signature tangy depth. If the mixture looks too thick, add 1-2 tbsp water to reach a pourable consistency.
Combine and Chill the Salad
Add the cream cheese mixture to the potato bowl and gently fold everything together using a large spatula. Be careful not to mash the potatoes—you want some texture. Fold in the 0.5 cup chopped Dill Pickles and 0.5 tsp Sweet Paprika for color and extra tang.
Transfer the salad to an airtight container and refrigerate for at least 2 hours (overnight is even better). This chilling time allows all the flavors to meld together perfectly. The longer it sits, the more the celery crowns will maintain their crisp texture while the potatoes absorb the creamy dressing.
Add Eggs and Garnish Before Serving
Just before serving, chop the 4 whole Hard-Boiled Eggs into small pieces and gently fold them into the salad. The eggs add a wonderful texture contrast and richness. Sprinkle with an additional 1 tbsp Fresh Dill and 0.25 tsp Sweet Paprika for garnish and extra flavor.
Serve chilled, straight from the fridge. The salad should be creamy yet still have that satisfying bite from the celery crowns. Each bite delivers the perfect balance of creamy, tangy, and crisp elements that make this Carnegie Deli version so special.
Pro Tips For Making Carnegie Deli Potato Salad
- COOL THE POTATOES RIGHT: Boil your Yukon Golds until fork-tender, then immediately drain and spread them on a rimmed baking sheet. Let them sit for 10 minutes—this prevents a gummy mess later, no matter how impatient you are.
- SWEAT THE ONIONS FIRST: Slice the yellow onion thin and cook it in a dry pan over medium heat for 5 minutes. The caramelized edges add depth, and it won’t turn your salad into a watery disaster when mixed later.
- THICKEN WITH CREAM CHEESE: Mix the full-fat cream cheese into the warm potato mixture while it’s still slightly steamy. This ensures it blends smoothly instead of clumping—no need to microwave it first, just work fast.
- CHOP CELERY SMALLER THAN YOU THINK: Slice the celery into ¼-inch pieces, not the usual ½-inch chunks. This even distribution keeps every bite consistent and prevents texture surprises when you take that first forkful.
Perfect pairings for carnegie deli potato salad
Classic Deli Sandwich
This potato salad pairs perfectly with the iconic Carnegie Deli Reuben sandwich—its creamy tang cuts through the smoky, sauerkraut-laden richness. Order the classic corned beef and Swiss combo with a side of your homemade salad for that true deli experience.
For a vegetarian twist, try the grilled cheese and tomato sandwich with extra sharp cheddar. 🥪
Grilled Meats
Serve alongside grilled chicken breast or pulled pork for a Southern-inspired spread. The tangy dressing balances the smoky flavors beautifully. I love using herb-marinated chicken with a lemon-pepper rub, or slow-smoked pulled pork with a touch of BBQ sauce.
For a lighter option, grilled shrimp skewers with garlic butter add a refreshing contrast to the creamy salad.
Summer Picnic Spread
Pack this potato salad in a mason jar with the dressing on top to keep it creamy, and pair it with crusty baguette slices, cherry tomatoes, and hummus for a no-mess picnic.
Add deviled eggs and pickled vegetables for a complete spread. For drinks, iced sweet tea or sparkling lemonade complement the tangy flavors perfectly. 🍹
BBQ Side Dish
This potato salad is a game-changer at backyard BBQs. Serve it alongside grilled burgers, hot dogs, or ribs for a crowd-pleasing side. The creamy texture contrasts wonderfully with juicy meats.
For a complete spread, add corn on the cob, coleslaw, and baked beans. Don’t forget the ketchup and mustard for dipping—it’s a classic combo! 🔥
Holiday Potluck Favorite
Bring this potato salad to holiday gatherings as a guaranteed crowd-pleaser. Pair it with roasted turkey, ham, or prime rib for a festive meal. The tangy dressing brightens rich holiday dishes, and the crisp celery crowns add a refreshing crunch.
Garnish with fresh dill and paprika for a festive touch that’ll make your dish stand out. 🎄
Beverage Pairings
For drinks, sparkling water with lemon keeps things light and refreshing. A crisp lager like Peroni or Budweiser balances the richness, while a dry Riesling adds an elegant touch for dinner parties. For a non-alcoholic option, ginger ale with a splash of lime enhances the tangy flavors beautifully. 🍺
Nutrition facts
Frequently asked questions
Why does this recipe use cream cheese instead of mayo?
Cream cheese creates a richer, tangier base that's more authentic to Carnegie Deli's signature flavor. It also prevents the salad from becoming too heavy or greasy. The vinegar and mustard balance the richness perfectly, giving that classic deli tang without mayo's heaviness.
Can I make this potato salad ahead of time?
This salad tastes even better after 24 hours as flavors meld together. Store in an airtight container in the fridge for up to 5 days. For picnics, pack it in a mason jar with dressing on top to keep it creamy while traveling.
What's the secret to keeping the celery crisp?
Cut celery into ¼-inch thick crowns and add them to warm potatoes immediately after boiling. Let everything cool completely before mixing with dressing. The residual heat helps maintain crispness, and avoiding over-mixing preserves the texture.
Can I substitute any ingredients?
For the dressing, use Greek yogurt instead of cream cheese for a lighter version (reduce vinegar to ½ tbsp). For potatoes, Russet potatoes work but may be less creamy. Skip eggs for a vegetarian version, but add extra pickles or bacon bits for texture.
How do I fix a watery potato salad?
Drain excess liquid from the potatoes before cooling, and avoid over-boiling them. If it's too wet after mixing, add 1 tbsp cornstarch to the dressing or let it chill longer to thicken. For immediate fixes, place the bowl in the freezer for 10 minutes to firm up.