Breakfast is substantial at La Olla, a traditional restaurant in downtown Oaxaca with a hot pink-and-marigold facade as vibrant as its cuisine. A heap of fresh string cheese sits atop a squash blossom omelet that blooms out over a dinner plate. A short stack of warm, pliant corn tortillas comes wrapped in cloth, accompanied by a small half-loaf of crusty-fluffy white bread. There’s butter, jam and red chili sauce, too.

But the sleeper hit of this spread is a small bowl of refried beans—velvety, aromatic, savory and piquant, a silky, seamless fusion of garlic, chilies, spices and earthy black beans. I slather it onto the tortillas, stuffing forkfuls of omelet into them. I eat the entire basket’s worth, then mop up the remaining puree with bread.

Refried beans were part of what had brought me to Oaxaca, but I admit, I arrived more enthused about the prospect of gorging on guacamole. But La Olla’s beans were a revelation. As I would soon discover, in Oaxaca, black beans not only anchor many meals, they also have a tendency to steal the show.

The first recipe Rodolfo Castellanos ever learned was refried beans. The boyish-looking chef, Oaxaca native and winner of Top Chef Mexico was taught by his mother, Doña Fuensanta, who also runs a nearby restaurant, one that caters more to locals than tourists. The mother-son pair agree to show me how they prepare the beans.

We meet in the cool open-air courtyard of Origen, a cavernous, whitewashed colonial mansion-­turned-restaurant that Castellanos opened in 2011. A myriad of ingredients are spread out on a rough-hewn wooden table: dried and fresh chilies, whole spices, fresh herbs, tomatoes and tomatillos, onion, garlic cloves and cooked black beans.

We begin over open flame, toasting pasilla chilies as well as avocado leaves—essential items in the Oaxacan pantry that resemble oversized bay leaves and add an anise-y undertone to dishes. Fuensanta grips the long, dried leaves with tongs and lets them singe over a stovetop burner. “Just enough to give them a tan,” she says. She crumbles the leaves over a white plastic bucket of cooked beans. The dark, leathery chilies follow.

The next step takes us to a molino, a community mill where residents can bring large batches of ingredients to be ground down to pastes. Scattered throughout the city, these shops are a crucial stop for cooks making mole, chorizo, hot chocolate, refried beans and more.

Inside the stucco storefront, five chest-high industrial mills are positioned over a drain set in a tile floor; hoses snake out from a pipe along the wall. With some added water, these powerful mills can churn through a sack of dried peppers, stems and all, to make a thin puree. Given our relatively small batch of beans, Castellanos says, “we are just playing.”

A worker empties our bucket of black beans into a mill’s wedge-shaped trough. He activates the machine and it whirs to life, quickly pulverizing the beans to a thick paste. At first glance, the puree could be mistaken for chocolate mousse.

Despite appearances, though, the mixture is a base that Oaxacan cooks turn to every day to make meals. This puree merely marks the start of a soup, a dip, a sauce or a filling that can be folded into tortillas in dozens of ways—making tacos, enchiladas, tetelas, memelas and tlayudas. It all depends on how you cook the puree.

This particular batch of pureed beans is destined for dipping. Castellanos and I return to Origen, where he drops a generous scoop of lard into an enormous steel pot. He lets it heat for a full five minutes, adding half an onion and a whole head of garlic to the pan. After the aromatics are charred, he scoops them out and discards them. The lard is blistering hot. That’s the moment to add the beans, so “it’s like a shock.” When the puree hits the lard, there’s a loud, long sizzle and a poof of steam.

Castellanos takes a spatula to the beans, whipping vigorously, constantly, for about 10 minutes. Not only does the movement prevent burning, he says, but it incorporates the lard into the beans, lacing them with meaty flavor. When they’re bubbling, shiny and thick, he knows the beans are ready. As he’s stirring and scraping, he describes how he could use the puree: thin it out to make an enfrijolada sauce, add stock or cream to make soup, use it in a tamale...

I get a taste a bit later, once Castellanos and Fuensanta have finished cooking our elaborate late-lunch feast. There’s spicy pork, a simple salad, fresh cheese, yellow mole and more, but what I keep returning to are the beans—creamy and rich as mashed potatoes, with a subtle smokiness and surprising depth. I even favor them over a bowl of guacamole.

Over a week in Oaxaca, I encountered more iterations: some smooth and saucy, with lots of chili heat; others more intensely aromatic, spiced with cumin and coriander. Each was a rebuke to my previous conception of refried beans, formed by mediocre Tex-Mex restaurants. Far from an obligatory side dish or an easy way to lard a burrito, they’re a daily staple—one that melds quintessentially Mexican ingredients in one cohesive dish.

Our first step at Milk Street was to adjust ingredients. Avocado leaves were sadly out. That had a more significant effect than we had anticipated—a side-by-side tasting revealed that they lent the beans much of their complexity, providing an herbal backdrop that also helped boost the other ingredients. We mimicked their flavor by using a combination of bay leaves, aniseed and dried oregano. And in order to offer a lighter-tasting alternative to lard, we also tested our recipe with refined coconut oil, which was a good substitute.

We made several changes to technique to account for the difference in strength between a molino and a food processor. The cooks we had met cooked dried black beans very basically—often with just epazote, garlic, onion and salt—then added more aromatics, avocado leaves and chilies later, just before processing. But we found it easier and more effective to incorporate the aromatics and chilies at the start of cooking. That also gave us a richly seasoned cooking liquid we could use to puree the beans.

We started by browning white onion, grape tomatoes and seeded guajillo chilies in lard or coconut oil, then added a pound of black beans, garlic cloves, bay leaves, aniseed and water. The beans became tender in two hours or less, depending on their age. (A pressure cooker softened them in just 40 minutes.) After adding salt, we strained them—reserving the cooking liquid—then pureed them in the food processor.

Next, we briefly bloomed cumin, coriander, dried oregano, smoky ancho chili powder and minced garlic in the fat; that gave our beans the depth of flavor we had enjoyed in Oaxaca without adding texture. We added the puree to the hot pan and stirred and scraped frequently until they were browned, thick and creamy—just like Castellanos’.