American potato salad suffers from the same affliction as its cousin, coleslaw: too much mayonnaise.

Sadly, the mayo is often an effort to mask a fundamentally unbalanced salad: unevenly cooked potatoes and hard-boiled eggs, a too-small shot of acid, an olio of underseasoned vegetables.

But this dish is the progenitor of Japanese potato salad, an addictively tangy upgrade of what’s found in American deli cases and salad bars. Creamy and smooth, not gloppy. Slightly sweet but tempered with savoriness.

It’s a product of yoshoku, Japan’s tradition of culinary cross-pollination with the West. It includes dishes like tonkatsu (fried pork cutlet), spaghetti Napolitan (ketchup spaghetti) and hambagu (a bunless, demi-glace-glazed beef patty).

Yoshoku began in the 1870s as a response to the Western physique. Europeans and Americans of the time were quite a bit taller than the Japanese, something the emperor and others attributed to their protein- and dairy-rich diets. That’s when ingredients such as butter and meat—which until then had been sidelined by Buddhism’s prescription to eat mostly fish, vegetables and tofu—were introduced to Japanese cooking, at the emperor’s encouraging.

Though mostly enjoyed by the upper class at first, yoshoku trickled into the mainstream by the 20th century. The dishes are Western in origin but distinctly Japanese in taste.

At first glance, Japanese potato salad could almost pass for its American forefather. But in Japan, cooks play up the supporting ingredients’ flavors rather than glossing them over with mayo. They mash a portion of the potatoes to enhance the salad’s texture. They salt the cucumber and carrot for better crunch and flavor. And while they use Japanese mayonnaise in equal measure, its flavor contributes savoriness.

For our version, we used Yukon Golds, which stayed firm when cooked but became creamy when mashed. We seasoned the potatoes with vinegar and pepper as they cooled for better flavor. Salting the vegetables firmed the carrot and cucumber and softened the red onion’s bite. we preferred the ease of grating for the carrot. Hard-cooked egg and ham gave heft, and an extra yolk, rice vinegar and sugar recreated the flavor of Japanese mayo (see sidebar).

As a final touch, we added a nontraditional ingredient, but one we found fitting: sliced scallions.