I heard rumors that Yakuts food was changing. Maybe it was all the new money or envy at the gleaming Uzbek and Georgian brasseries popping up in Moscow or just ethnic aspiration, but supposedly the indigenous Yakuts of Eastern Siberia have decided it’s high time their traditional frozen horse blood and fishy concoctions and reindeer organ stir-fry received the full-on haute cuisine treatment.

The epicenter of Yakuts culinary innovation is the city of Yakutsk, population 250,000, and a 400-year-old monument to perseverance. It is, give or take, the coldest city on earth, settling in on -40 °F during the long winter. Which makes summer feel like a Siberian joke: temperatures skyrocket to 100 °F and mosquitoes swarm so thick that I’m told they feel like a second skin. There aren’t a lot of fresh vegetables, fruit, or anything else harvested from the ground. People depend on protein – reindeer, horse, moose and above all, fish from the massive Lena River that courses through the city and from which Lenin, then in Siberian exile, derived his name.

Yakutsk is not an easy society to penetrate, and so I went looking for a guide.

Slamming the door behind the icy air ricocheting along Lenin Prospect, the main drag in Yakutsk, I scanned the restaurant for the man I was scheduled to meet. A hand shot up from almost next to me.

“The name is Basil.”

I swiveled to find a nattily dressed, very round, very short man cradling an electronic book reader and a tall cup of tea. The English accent was so upper crust I thought it may have been last heard in the bunks of Eton around when Harold Macmillan was prime minister.

Basil, who was educated in the 1980s at Moscow State University and now worked for a politically connected Russian foundation, must have noticed my gaze on the prodigious mound of green salad heaped in a bowl in front of him because he arched an eyebrow and said, “I quite like vegetables, you see. I am aware this is unheard of for a Yakuts man.”

I sat down. Basil was eager to talk, to tell me how much his eastern Siberian city—a backgammon configuration of shoddily built new midrise developments and grim Soviet apartment blocks, along with a few teetering Tsar-era wooden buildings—had changed since Soviet times. “I brought some Japanese people here in 1991, you see, to the government hotel. Absolutely horrible building, you see. Then I took them to this restaurant, it was really a canteen; they had incredibly bad material for cutlery, and the toilet wouldn’t work. The first thing the Japanese saw was a huge, enormous head of an elk. They were shocked as Japanese people always are to see any dead thing. A Yakuts guy walked in with no nose and no earlobes, which had just been cut out in some kind of street brawl. You are, of course, aware, when Japanese people see blood they get incredibly upset.” Basil forked a vegetable.

Yakutsk doily culture

Yukutsk exists on the edge of what is humanly survivable, but the economy hums. New construction booms, the city is a historic center for state universities, and the region produces a large share of the world’s diamonds. Men have to be flown in from elsewhere in Russia and Central Asia to work the mines.

Amid the heavy industry, Yakutsk supposedly has taken on some culinary glitz. “There are some young chefs are who trying to push things forward,” said Basil. “But it’s very difficult because the Yakuts people, to be very blunt, they don’t want to have any sort of new fusion inventions. They’re conservative.”

We decided to take an immediate field trip to Tygyn Darkhan, the hotel restaurant whose chef, a Mr. Tarbarkhov, everyone in Yakutsk apparently agreed, had launched new wave Yakuts cuisine. “He’s the guy who actually started the whole thing,” Basil explained as we walked. “Before him there wasn’t any Yakuts food designed in any sort of acceptable form, it was just food poured together. No appetizers, no entrées – but he regimented the whole thing like European cuisine. Russians loved it, but before him it was only for native people. He elevated it to a restaurant level.”

Mr. Tarbarkhov did have one precursor. Yakuts food, according to local lore, was first lashed to Western technique in June, 1944 when Henry Wallace, FDR’s vice president, traveled through Siberia with generals from the NKVD—Stalin’s secret police—where he toured gulags and declared the brutalizing slave labor camps to be full of contented volunteers. When he got to Yakutsk he was served local ingredients elegantly prepared continental-style by trained cooks flown in from the Baltics.

Tygyn Darkhan was just around the corner, but since Basil had just eaten his enormous salad we decided to limit ourselves to a snack. Mr. Tabarkhov, for reasons never made clear, declined to step out from the kitchen, but the waiter was eager to show off the chef’s signature disk, a plate of half-frozen, congealed horse blood shaved into thin slices called haan, which, logically enough, means blood in the Yakuts language. According to tradition, the blood must come from a colt no older than six months (the rule for most Yakuts horse recipes). Eaten with your hands, the sticky pieces are dipped into table salt before chewed. Odorless and initially close to tasteless, haan warms quickly with saliva, feeling like a tiny plop of raw hamburger bit crumpled on the tongue followed by a distinctive aftertaste of, well, blood, not unlike the taste sensation of the drip from a light nosebleed.

Haan: thin slices of colt meat

Next came Stroganina, the name for strips of raw fish commonly found across Siberia, and in this case an attractive geometric array of translucent whitefish from the Lena River also served shaved, frozen. Then followed Pechen (or Pakha depending on the location), a generous plate of raw horse liver embroidered with little droplets of raw horse fat. This, too, was served shaved and refrigerator-cold. With both, the experience was similar as with the haan: initial tastelessness yielding to an essence of fishiness or of horse organ-ness, almost like an experimental raw-food-perfume lightly spritzed onto the tip of my tongue.

Basil was delighted. “If this stuff isn’t frozen it just melts away completely.” Then he frowned. “Of course, it’s not healthy to eat a lot of it.”

And with that, Basil launched into the sordid tale of his uncle, who was a medical professor, a former executive director of the Yakutsk Institute of Health, and a fierce champion of the health benefits of Yakuts cuisine: “He was the leading light of the medical profession here and he made a life cause out of promoting the health of Yakuts food,” Basil began. “He’s a local authority and everyone knows about him. He traveled to Moscow and to many conferences claiming the flesh of the Yakuts breed of colt, the yearling but not the grown horse, has special properties. Unfortunately he undermined his cause by having several heart attacks at an early age. He also has a huge case of sclerosis. He claims he actually discovered very special unsaturated fat in Yakuts food, and this fat comes into collision with the bad fat and neutralizes it. He also claimed it protects people from radioactivity. Complete pseudo-science, you see, and, as I said, there were the many heart attacks.”

The following week, I met Basil at a restaurant-bowling alley complex on Petrov Street called Mukhaya. A young local chef, Nickalai Gabyshev, who is actually ethnically Russian but a Yakuts cuisine specialist, created a buzz by using French and Turkish technique and supported his innovation with a scaffolding of Asian spices.

“I think probably Yakuts food can be as good as any other,” the chef said. His presentation is dramatic: vertiginous stacks of firm whitefish tied with bright green chives, or strips of raw horse meat twirled around a plate like torn red carnations. Gabyshev likes to rethink traditional recipes by, for example, scattering dried sea cucumber into pickled cabbage and river fish, or using sous vide to prepare a thick cut of horse steak.

One of Gabyshev’s creations

Chef Gabyshev said he wanted to present a sampling of the menu so we sat back and waited. I made only one request: no frozen horse blood.

Soon my friend Yulia, a 28-year-old Yakutsk native, and her three-year-old daughter, Vlada, joined us. Neither had really tried Yakuts food before, not unusual for ethnic-Russians in the region.

The first plate: a kaleidoscope of raw horse chunks, velvety red and laden with thick fat. Basil announced he’s not touching it, although he did, quite a bit as a matter of a fact. Yulia also renounced the meat and stuck to her guns. Vlada would have none of it. I staked out a middle ground, gingerly poking at the leaner cuts. The cold meat looked repellently oily, almost sweaty, but the tang of raw flesh meshed well with the briny-sweet grit of the fat, almost like butterscotch, and I had the urge to wash it down with a shot of vodka.

The second plate: a pile of flakey white fish that looked like a stack of overstuffed white envelopes. A drizzle of liquefied green herbs perforated the top. I was slightly astonished to discover the fish had the bright richness of grilled sea bass or black cod, and the herb glaze added a luscious finish. Yulia said she was impressed and more than a little surprised. Vlada passed.

The third plate: a reindeer stir-fry that looked and tasted a lot like Mongolian beef ordered from an American Chinese take-out. The charcoal black reindeer meat was pleasantly chewy and dense, I thought, satisfactorily. Basil started to say something but instead returned to the fish. Yulia objected to the spices and the reindeer’s texture. Vlada didn’t want it. I was starting to think Vlada was pretty useless.

Soon more dishes piled onto the table and Chef Gabyshev sat down to discuss his cooking ambitions. “Yakuts food is an embryonic state,” he said. “There is incredible resistance to change of tastes in our food, and some dishes I serve unaltered, like the blood sausage in horse intestines. But generally I’m trying to convince local people to accept some foreign tastes and I want foreign people to give Yakuts ingredients a chance.”

Nickalai Gabyshev

But for that to happen, Gabyshev said, Yakuts food will need to cut down on the fat content while emphasizing what’s most appealing to outsiders. “To be popular elsewhere it has to be adapted because it is so highly caloric,” he said. Arranging the pile-up of empty plates, he continued: “We have fresh ingredients only available here. The fish is extremely tasty because it’s caught in minus 40 degree conditions and it simply has not been tasted anywhere outside the region. The same applies to the horsemeat. They kill the little horses when they just stop sucking the mother’s milk, that’s why the meat is extremely fresh and soft.” Basil nodded. Yulia looked slightly sick.

Another Yakuts competitive advantage: wild game. “We use our wild Siberian chicken, the wild hare, all sorts of wild animals. Moose is delicious but it’s very rare in a restaurant, you won’t see it,” said Gabyshev.

A couple of weeks later, Basil invited me to his cousin’s house for dinner. His cousin, a construction and mining mogul, was cooking horse flank. “He’s not like many Yakuts people,” Basil said. “He’s curious about the world, you see. He’s a quite interesting character. Also I believe he is personally worth 200 million dollars.”

The cousin turned out to have a lot to say, and we sat submissively on his couch while he lectured us on Turkish influences on Yakuts culture and language, on the advisability of placing a large order of Caterpillar heavy-duty tractors, about the crisis in Syria, and whether the iPhone 5 is worth the upgrade. When I asked for a refill of water the cousin asked his teenage son to take my glass to the kitchen. The boy had been glaring at us with undisguised hostility. “You should pay me,” the son said to his father.

After about an hour of this, the cousin took us into the kitchen to show us the gigantic slab of horsemeat steak. The preparation would be severe: no seasoning at all, not a drop of oil or butter; just meat cooked for exactly –“very, very precisely,” the cousin insisted—two minutes in a bone-dry cast iron skillet at a very high heat.

We sat at the kitchen table, each had a goblet of expensive French Bordeaux purchased at a duty free store and a glass of kumus, fermented milk that the cousin had made from a batch of culture he had brought from Kyrgyzstan. With stupendous flourish he turned on the flame and, slightly bent toward the stove, watched the meat heat in the dry skillet for two minutes. And then, for at least another fifteen minutes. Basil and I looked at each. The smell of burning flesh permeated the small kitchen. Stabbing the meat with a carving knife, he served us.

It was, without a doubt, exquisite. Tender and moist, the steak soared into a stratospheric perfect. Crusted on the edges with a ravishing burn, the pink inside jangled my taste buds ecstatically. I looked over at Basil. He raised one eyebrow; brick-red juice was swimming down his mouth.

It was the most delicious meal we shared.

Ilan Greenberg is a freelance journalist who has contributed to the New York Times Magazine, Slate, and the Wall Street Journal, among other publications.