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.

Kewpie, the tangy, eggy mayonnaise of choice in Japan

The meaty flavor in traditional Japanese potato salad isn’t from ham alone; the mayonnaise also beefs up the umami quotient. That’s because, in Japan, the mayo brand of choice is Kewpie.

Some of Kewpie’s dimension comes from monosodium glutamate (MSG), the controversial but indisputably flavorful ingredient found in Goya Sazon and Maggi seasoning. But MSG only helps round out Kewpie mayonnaise’s flavor. Rice, red wine and cider vinegars give it sweet acidity.

Toichiro Nakashima debuted Kewpie in 1925 after trying mayo in the U.S. His hope was to improve the physique of the Japanese people—prompting him to double the amount of egg yolk in his recipe. Today’s Kewpie uses yolks exclusively.

In Japan, Kewpie is slathered on omelets, pizza, noodles, sushi, pancakes, rice balls, even fruit. One Tokyo restaurant deals solely in mayo-based items, including fondue, milkshakes and margaritas. If you’re curious to try Kewpie, look for its distinctive packaging: a teardrop-shaped bottle bearing the bright-red likeness of a Kewpie baby doll.