And that, dear comrades, is how you concoct fisinjan, the Azeri version of a chicken, pomegranate, and walnut stew of Persian origin that hereabouts comes black as the blackest Oaxacan moles and just as layered and rich. "Screaming scares the stew into blackening," Mehriban explains matter-of-factly. And if it doesn't do the job, why, oxidation from the horseshoe and nails will.

Welcome to Azerbaijan, a onetime Soviet republic, where you'll dine on fisinjan and other saucy (though un-nailed) stews called khurush, along with ethereal pilafs bejeweled with dried fruits, nuts, and barberries. Where the table is always laden with lavish sprays of whole opal basil and tarragon. Where you'll wrap briny village cheeses in flatbreads, dab tart homemade yogurt on fluffy omelettes called kükü, and savor lamb so flavorful it doesn't need salt. Then, over quince compote (or vodka), you'll gossip (surely) about another Mehriban—Mehriban Aliyeva, the current first lady of Azerbaijan, who looks like Gina Lollobrigida and loves launching eye-popping new cultural projects.

The tarragon, the saffron-stained rices, the sexy accents of unripe plums and verjus, the gigantic stuffed meatballs bobbing in broth—they are one reason my boyfriend, Barry, and I have returned for the second time in a year to Baku, the windy capital of this Caspian country of close to 10 million people wedged in between Iran and Russia in the easternmost corner of Europe. This most fascinating of places has a Turkic language, heavy Russian cultural baggage from its years attached to czarist and then Soviet empires—and the world's last great undiscovered cuisine, mostly indebted to sophisticated Persian palace cooking but with enticing inflections of Georgia, Russia, and Ottoman Turkey.

As a former Muscovite born in the USSR, I've brought my own family baggage to Baku. During World War II, my grandfather Naum, then a dashing Soviet intelligence chief, was stationed here to help prepare for the Tehran Conference—the first meeting of Stalin, Roosevelt, and Churchill, held south across the Caspian Sea. His family, including my 7-year-old mother, joined him here.

Mom still describes Baku as an Orientalist mirage amid the devastation and hunger of wartime. Fishing in the Caspian was Naum's spy cover. His aides, she recalls, would haul in a sturgeon the size of a sailor, split open its stomach, and scoop out the caviar. To this day, she can't look at fish eggs without feeling guilt at her family's luck while the rest of our ravaged country was starving. Equally vividly, my mother remembers Baku's stench of petroleum.

Oil. It was why Hitler veered calamitously toward Baku, but his Luftwaffe held off bombing. The Führer wanted the city's vast energy reserves intact. Since ancient days, oil and natural gas have fueled the unexpiring flames of Azerbaijan's Zoroastrian cults, and now they underwrite post-Soviet Baku's futuristic high-rises, malls, and Dubai-worthy starchitect showstoppers—while the city's ornate fin de siècle facades testify to the late 19th-century heyday when Azerbaijan pumped half the world's crude and local peasants turned overnight into oil barons. On my previous trip here I'd ogled the fantastical architecture, toured a Zoroastrian fire temple, and filled a plastic bottle, amazed, from black oil pools oozing in the arid moonscape outside Baku. And then I met Zulya, cousin of an Azeri friend in New York and such a fiercely formidable cook that the trip turned into my own Ottolenghi-esque mirage of charred eggplants, yogurt swirls, and dried rose blossoms.

So now I'm back, to pry out Zulya's and her mom's kitchen secrets. In between dolmas and pickles and syrup-drenched sweets, I'll try to untangle Baku's complicated cultural layers.

Mehriban, Zulya's mother, lives between Burberry and Dolce & Gabbana boutiques in a graceful 19th-century quarter—not the kind of hood, you'd think, where folks ritually scream at their pots. Entering her building, Barry noted the tomato-red Maserati parked across the street outside Z-style, a chic takeout food shop Zulya owns with her husband, Rufat. Mehriban belongs to a caste of old Soviet-educated elites. A former engineer, she's married to Azerbaijan's retired traffic-police chief. I prod her now about the horseshoe in the simmering fisinjan stew. She shrugs. "It's how they do it in Lankaran," she informs me, "my birth city of amazing cooks down on the Iranian border." Soviet times, though, were very different, annotates Zulya. "Then Mom mostly cooked borscht and stroganoff. My parents vacationed in Moscow." But the folkloric foodways held fast in Azeri DNA—and I'm now primed for Mehriban's plov, or pilaf.

Anyone familiar with Iranian cooking will recognize the basic pilaf technique: Dump aromatic basmati rice in a huge pot of water. Drain when half done. Steam again long and slow under a towel-swaddled lid until each grain is as eloquent as an Omar Khayyam quatrain. Most crucially, line the pot with lavash or a layer of rice mixed with butter and yogurt to create that addictively crunchy bottom crust called kazmag (tahdig to Iranians).

"In Azerbaijan we have perhaps 200 plovs," proclaims Mehriban. "I know at least 50." For now, she's showing off the borani pilaf, steamed with pumpkin cubes drizzled with sweet condensed milk and eaten with smoked kutum, a Caspian whitefish. The funky contrast of sweet pumpkin, buttery rice, and salty shreds of kutum is reason enough to fly to Baku. Ditto the stuffed cabbage Zulya supplies, not the leaden Slavic variety but delicate pouches elegantly filled with meat, dried fruit, chestnuts, and herbs.

As I watch Mehriban reach for enormous jars of preserves—white cherries, rose petals, and feijoa, the intoxicatingly fragrant pineapple guava—to accompany our sage tea, I try to unpack the Azeri obsession with preserves and compotes: Ottoman influence or Soviet-era fixation with putting up everything dictated by shortages? Mehriban's household is its own cultural mash-up. Turkish soap operas blare on her Azeri-channeled TV, while beyond a flimsy partition, her husband, the ex-traffic-police chief, watches old Soviet films on his own TV.

The next morning Barry and I survey Baku's architectural mix from our 18th-floor window at the Marriott Absheron, our glossy high-rise hotel near the Bay of Baku. The Government House, a Soviet-Gothic relic of Stalinist gigantomania, hulks right below. In the distance, the Flame Towers, a trio of wavy 2012 glass-and-steel skyscrapers, loom like friendly earthworm monsters from a Miyazaki film. Closer, Beaux-Arts oil-boom mansions line Baku Bulvar, the leafy promenade running along the crescent-shaped Caspian waterside. Just inland, the UNESCO-protected walled medieval Persian Old City has been pristinely restored, a stage set of honeyed-sandstone hammams, caravansaries, and carpet shops. Its highlight is the squat Maiden Tower, a marvel of 12th-century brickwork that looks uncannily art deco.

Then again, not even an architect could tell which layer is which, because recently the whole city center has been sandblasted, refaced, and melodramatically lit to resemble Haussmann's Paris—by way of Vegas—at the whim of first lady Mehriban, a 24-karat Francophile. And yet Baku isn't an artificial desert folly like Dubai. The history behind its faux-French facades is real and resonant.

Zulya now swings by in her praline-colored Mercedes to whisk us to Yal Bazar, her favorite market. Tanned, coiffed, and sporting torn skinny jeans over Gucci wedges—a vision of Baku by way of Beverly Hills—Zulya had never planned to become the city's premiere food diva. She trained as a concert pianist. But as a teenager, she says, she was more seduced by the frilly Soviet tortes baked by Valya, their Russian neighbor, than by sonatas and nocturnes. She begged Valya for recipes, surprised her parents with perfect éclairs, pestered Mehriban to recall old Lankaran dishes. In 2000, on a whim, she opened Z-style in her father's former garage space. "On opening day I stood mortified," she recalls. "Customers swiped every last piroshki from my lovingly arranged display!" That night an earthquake shook Baku—but the next day Z-style was even more mobbed. Now with five Z-style shops, a thriving catering business, and a new Caspian-side restaurant about to open, Zulya aspires to be Baku's Ottolenghi (her hero).

Like everything in Baku, the Yal market is extremely clean, more boutique than souk. Black and white mulberries are arranged in precise checkerboard patterns; pretty baskets overflow with fava beans and thin wild asparagus. In a spice row Zulya sifts bejeweled fingers through artful pyramids of plump, tart zirinc (dried barberries) and sumac in every shade of purple and burgundy.

"What decadence!" she gasps in the preserves and pickles shop, where for one jam they stuff each yellow cherry with walnuts. Farther on a lady is selling fig vinegar, abgora (verjus), homemade rose water, and narsharab (pomegranate molasses) under a portrait of Lenin. At each stall Zulya schools me in Azerbaijan's fruity-tart-herbaceous seasonings. "These flavor levenghi, the walnut paste for stuffing chicken or fish," she says of the sundried fruit leathers that shine like sheets of edible fabric in flavors such as cornelian cherry. These plums? Puckery green alycha brings zing to herbed stews; amber dried albukhara commingles with chestnuts in a khurush called turshu govurma, or fills giant soup meatballs that Zulya plans to prepare. We stop at the verdant sabzi (greens) counters loaded with some 20 species of herbs.

"Herbs are essential to our Azeri table, as palate teasers by themselves," says Zulya, "and as elements in our dishes." Here's tarragon for chopping into dovga, a refreshing cold yogurt soup, and kever (garlic chives) and cilantro for a green stew called sabzi govurma. "Ours is the world's greenest cuisine!" Zulya declares. A strange thought, given that Baku sits on a diabolically parched, dusty peninsula.

After the market comes a quickstep food crawl: some gutabi to start, floppy filled flatbreads singed on convex griddles inside the Old City; then a whole Caspian fish, crisp-fried then braised in a luscious sour plum sauce at a waterside fish restaurant on the southern edge of town; then a pastry high at Zulya's nearby catering kitchen—where smiling white-coated dames brush syrup over 14 layers of pakhlava, stencil elaborate herringbone patterns on pastries called shekerbura, and shape mutaki (dainty sweet rolls) around cardamom-scented walnuts.

Heading back, we stop at the Bibi-Heybat Mosque, perched above a hauntingly ugly-beautiful graveyard of rusting old oil derricks and tankers. The mosque is a venerated 13th-century shrine that was destroyed by Soviet atheists in 1936, then resurrected with showy sleekness in the '90s with the blessing of Heydar Aliyev, Azerbaijan's monumental ruler, now dead and succeeded by Ilham, his (less monumental) son. Azerbaijan is a paradox: a predominantly Shiite country whose citizens love Russian vodka. Another paradox: Heydar Aliyev, who was an atheist, communist KGB chief before he started blessing mosques.

In Baku, Aliyev père is immortalized not by a somber stone mausoleum but by a swooping, quasi-extraterrestrial fantasia of white curves that, from some angles, resembles whipped cream piped in from the cosmos. I mean the Heydar Aliyev Center, one of Zaha Hadid's most breathtaking buildings. Here in this white apparition conjured by power and petro-fortune, we behold Heydar Aliyev's vintage cars, Heydar Aliyev's many medals, Heydar Aliyev's manifold gifts from other world leaders. (Putin gave a macho rifle; Romania's president, an old-ladyish tea set.) There's some space for international art exhibitions, too, and a pretty swell ethnographic museum.

"At least someone's willing to spend a country's billions for global cachet," Barry quips the next day, as Zulya's husband, Rufat, threads sweet nuggets of sheep's tail fat onto skewers. We're gathered at Mehriban's dacha, a short drive east of Baku, for a multigenerational family feast to celebrate Azerbaijan's Independence Day. By late afternoon, Mehriban's airy bourgeois kitchen is a green, aromatic blur of parsley and chives sautéed for the sabzi govurma, of dill bouquets snipped for the herbaceous pahla plov, a delicate pilaf studded with fava beans. Eggplant whirs in the food processor for the baked kükü omelette textured seductively with walnuts and barberries. Mehriban is stuffing softball-size meat orbs with dried fruit. These will be floated in saffron broth with chickpeas and chestnuts in küfta bozbash, a soup garnished with a zesty flourish of sumac-dusted onions.

Because one pilaf is never enough, Zulya now brings her celebratory rice tour de force out of the oven. It's called khan (also shah or something else royal) plov, and it's rice baked inside a golden lavash pastry case bathed with a truly indecent amount of butter. Whoosh! Zulya inverts the royal pilaf onto a platter. Crunch! She slices open its casing. And a fragrant cargo of saffron rice, barberries, candied lemon peel, dried fruit, chicken, and nuts—Zulya's modernized take on the classic—cascades out of the pastry. Toasts ascend to the sky. I marvel at the bright bowls of trompe l'oeil cherries and grapes decorating the table; they look fresh but are actually pickled. As a Muscovite with homes in New York and Istanbul, I feel as if all my life I've belonged at this generous Turco-Russian-Persian table. Rufat refills our glasses with vodka. I think of the complicated Soviet past we all share, of my small mom finding a brief wartime paradise in Baku, of the natural resources and geopolitical forces that have separated our former "fraternity" of Soviet republics into the haves and have-nots…of all the Azeri dishes I still haven't savored.

Zulya taps my shoulder, as if reading my mind. “Anya…Anyechka,” she cajoles. “Next time you come to Baku, we'll make you a whole huge Caspian fish stuffed with walnuts!”