There are two types of potato eaters: people who see them as a carrier for salt and fat, and people who actually enjoy their earthy sweetness and slightly bitter flavor. Show me a bowl of potato salad, and I will tell you which kind of potato eater prepared it.

This is not to say you can’t dabble in both camps. While I prefer my mashed potatoes be as simple as possible—simmer them directly in milk for the most streamlined approach—I am not above a fully loaded baked potato, or fully loaded baked potato-inspired potato salad. I like fun! But a potato salad that respects the potatoes, one that takes the time to develop the flavor of the spud itself and then complement it rather than obscure it—that’s my Platonic ideal of potato salad. Our Grilled Mustard-Herb Potato Salad is such a dish.

Grilling the potatoes gives them real character

Most potato salads start with boiled potatoes, which gets them cooked but readies them for a background role—one that plays second fiddle to the mayo-based dressing and salty and/or fatty inclusions. The high heat of the grill gives them character and makes them the star. The skins crisp and char, adding texture and smoke, playing against the sweetness and amplifying the inherit bitterness.

Then they are ready to receive a bold, complementary dressing—one without mayo, which would only hide their light under a bushel. But I’m getting ahead of myself. Before you can dress the potatoes, or even toss them on the grill, you have to boil them a bit.

A bit of boiling helps them keep their shape

Potato salad textures exist on a spectrum, starting with those that are more of a cold, unctuous mash than a true salad, running all the way to whole, toothsome potatoes tossed in a bold, clingy dressing. This one is on the latter end of the scale. We start with small, unpeeled Yukon Golds. It’s tempting to immediately toss them on the grill, but that can be a challenging affair; even small potatoes tend to scorch outside before becoming tender inside. It’s a problem that’s easily solved with a little parboiling, however.

Using plain water will render the potatoes fully cooked, but bland and mushy; A couple of common pantry staples can fix both issues. Salt in the cooking water takes care of the flavoring, and vinegar lowers pH, which helps the potatoes keep their shape in two ways: Potatoes get their structure from hemicellulose, a carbohydrate present in almost all terrestrial plant cell walls. It breaks down fairly easily in hot water, but hemicellulose is not very soluble in an acidic environment. Add a little acid—or cook it in an acidic substance, like tomato sauce—and it will keep its shape much longer than it would in plain, neutral water. Boil a potato with a little baking soda, however—which raises the pH into alkaline territory—and it will turn to mush.

There is a second substance in potatoes that’s affected by acid. Like most plants, potatoes are held together by pectin, a soluble fiber famous for helping jams get jammy. When plants are cut up and cooked, the pectin gets discombobulated, dissolving into a watery, mushy mess. These freed molecules accumulate a negative charge, which repels them from one another, so they cannot form a gel. (Think of two magnets with their like poles pointed towards each other.) Luckily, it is very easy to change the charge on these mushy molecules: Add a little acid, which has a positive charge. This neutralizes the negativity, so the pectin can cozy up and bond. If you were looking to set up a strong gel, like in jam making, acid alone would not be enough—you would need to add sugar (which draws water to itself) and boil off excess moisture. But we are not making potato jam, so adding acidic vinegar is plenty effective.

You don’t need a ton, just 5 tablespoons for two pounds of potatoes is enough to ensure your potatoes come out tender and creamy without falling apart into a messy mush.

Get a grill basket for even charring

After about 15 minutes of acidulated boiling, the potatoes should be tender enough to pierce with a skewer without meeting much resistance. Now they’re ready for the grill. You could throw the spuds directly on the grates, but you’ll need to be vigilant about turning them with tongs, and they may brown and char spottily, even under a watchful eye. We found a sturdy perforated metal grill basket with a broad bottom is best for managing the potatoes over the fire. You don’t have to worry about small potatoes falling into the coals, and a basket provides a flat heat-conducting surface that helps with browning.

Spotty charring isn’t the end of the world, however. Even if you don’t have a grill basket, the flavor will still be excellent.

Use mustard as your salad glue

It would be a shame to develop all of that smoky, bittersweet flavor and creamy, tender texture, only to obliterate both with globs of mayonnaise. While mayo is an effective binder and emulsifier, it’s not the only condiment capable of holding a salad together.

Mustard, especially one that is high in mucilage, is an incredibly effective emulsifier—a stellar food glue that keeps your potato salad creamy and cohesive. In addition to being a terrible sounding word, mucilage is a thick, gluey substance found in plants, most famously okra. You can also find it in the outer coating of mustard seeds, though not all prepared mustards are high in mucilage. (I’m looking at you, classic yellow.)

Stoneground mustards and Dijon both contain a fair amount, however, and this potato salad uses the latter to ensure the dressing has maximum clingability. Whole-grain mustard brings a pleasant texture, and a little olive oil ups the richness. Toss while warm, then finish with a final splash of vinegar and handfuls of fresh herbs and serve warm or at room temperature alongside grilled meats, vegetables or seafood.

Want more No-Mayo Week at Milk Street? Learn how to ditch mayonnaise for more flavorful salads; Watch Rosie Gill use miso to make a better chicken salad; Meet the Austrian potato salad that Christopher Kimball dubbed "the world’s best"; And let Wes Martin show you how to make an all-egg egg salad.

Join the conversation on Facebook, Instagram, TikTok and Pinterest.

And if you're looking for more Milk Street, check out our
livestream cooking classes with our favorite chefs, home cooks and friends for global recipes, cooking methods and more.