On a visit to Birmingham, writer Lettie Teague discovers exceptional wine directors at supermarkets but an odd absence of sommeliers at restaurants.

Birmingham, Alabama, deserves a sommelier. The last one of note left town about three years ago. Everyone I talked with knows his name and his story. And everyone was sorry to see him go. But as one grocery-store wine director said to me, "Birmingham really isn't ready to support a full-time sommelier." Yes, a wine director in a grocery store made that observation. And such is the puzzle and the challenge that is the wine scene in Birmingham.

There is a backstory, and it begins with Frank Stitt—otherwise known as the man who put Birmingham on the culinary map. Stitt studied cooking with luminaries Alice Waters, Richard Olney and Simone Beck, then went on to win just about every possible chef award imaginable. He also spent time at Paris's L'Académie du Vin at the invitation of its founder, Stephen Spurrier, the wine merchant who created the famous Judgment of Paris tasting of 1976. In fact, Stitt is easily the most wine-knowledgeable chef I've ever met. Yet he was the one who hired—then said good-bye to—that lone sommelier. I learned all this when I went to Birmingham recently in search of an answer to a question I'd been mulling over for a while: Is a great food city always a great wine city too?

Birmingham, by all reports, easily qualifies as the former. In fact, it has earned a national reputation for extraordinary restaurants like the Hot and Hot Fish Club, owned by chef Chris Hastings, and Café Dupont, run by New Orleans–trained chef Chris Dupont. And of course, it's known for Stitt's four restaurants, most famously his flagship, the Highlands Bar and Grill.

Lettie Teague on Natural Wines:

I've met people who know almost nothing about Alabama or, for that matter, Birmingham (save, perhaps, for its notoriously troubled racial past) but have nevertheless heard of the Highlands Bar and Grill. It's that much of a landmark. I chose my hotel, the Hotel Highland at Five Points, because it is located a few blocks from the restaurant.

All of Stitt's restaurants—as well as the Hot and Hot Fish Club and Café Dupont—are in downtown Birmingham, while all the top wine shops are in the wealthy suburbs, or "over the mountain," as the locals say. (This mountain is made of ore, and it's the reason Birmingham was once called "the Pittsburgh of the South"—back when that was considered high praise.)

My tour of Birmingham began in its suburbs. I'd been told that Classic Wine Company, in Homewood, had a terrific European wine selection. So I was a little surprised to see that the store was in a drab former bank building, where the drive-in window didn't dispense cash, or even wine, but was instead dominated by a large cat bed. The store's interior was equally unremarkable, though its wine selection was quite good. The Châteauneuf-du-Pape section contained several vintages of the great Château de Beaucastel, imported by Birmingham-based Robert Haas of Vineyard Brands. (Sometimes it's good to have an importer in your city; I've never seen so much Château de Beaucastel outside the Rhône.) There was also a surprisingly diverse array of Loire Valley wines, including those from one of my favorite producers, Olga Raffault. When I praised the selection to the proprietor, Tony Meyer, he informed me that a Birmingham family owned a Loire château.

Meyer was a retired physician when he opened his wine shop some 20 years ago, at a time when most Birmingham residents bought their bottles out of state, in New Orleans, Atlanta or even as far away as Washington, DC. Now Birmingham residents have excellent choices in their own town and are quite sophisticated about wine, according to Meyer, who noted that they favored California wines most of all, especially Chardonnay and Pinot Noir.

At the Village Wine Shop in Mountain Brook, South African Pinotage seemed to be the favored varietal; I've never seen so much of it in one store. Manager Thomas LaBoone loves these wines and is particularly keen on a label called the Chocolate Block. "Some people call us the Chocolate Block store," LaBoone said. "There is a real cult around the wine." This Rhône-style red is a textbook example of clever packaging, and its catchy name is a brilliant move by a winery with the unpronounceable moniker Boekenhoutskloof.

LaBoone runs a small wine school in the back of his store, and he showed me the bottles his class would be tasting that night. It was an ambitious lineup: a Grechetto from Umbria; a Pinot Noir from Baden, Germany; and of course, a Pinotage from South Africa. At the top of the handout, LaBoone asked students to write down "a couple of questions you have always wanted to ask about wine." The most common queries were about blends, according to LaBoone. "People always want to know if a blend means there's something wrong with the wine." The strangest question? "A man once asked me, 'How do you tell if a bottle is red or white before you open it?'"

There was no Pinotage on the wine list at the Hot and Hot Fish Club, but there was plenty of American Cabernet and Pinot Noir. The choices were very good but predictable, like Honig Cabernet from California and Ken Wright Cellars Pinot Noir from Oregon. The list just didn't match the sense of adventure in the menu, which featured dishes like Hangtown Fry with eggs, fried Apalachicola oysters, spinach and house-made pancetta, and the Fudge Farms Pork Trio (belly, loin and leg). All showed a clear mastery of flavors and textures.

When Hastings stopped by after dinner to introduce himself, he waxed rhapsodic about his food purveyors and farmers, each of whom he knew by name. "Every plate is a story of someone's life," he said. The duty of describing the wine list fell to one of the waiters. "He's also in charge of educating the staff," Hastings said. "We don't have a sommelier; we would rather make an effort to educate our servers." But, he added, he was nevertheless going through a "major rethink" of his wine list.

There was also no sommelier in attendance at Café Dupont, where I'd arranged to have lunch the next day with two local wine salesmen. I loved Dupont's fried oysters and cornmeal-crusted shrimp. Like Hastings, Chris Dupont clearly reveres ingredients (Fudge Farms was another favorite purveyor here), but his wine list played it safe. In fact, it was remarkably similar to the one at Hot and Hot. "I'd like to see more variety on wine lists in Birmingham," said one retailer, who then promptly ordered a Pinot Noir, the same one I'd seen at Hot and Hot.

Frank Stitt clearly cares about both food and wine—with a passion. In fact, he was tasting with a French-wine salesman at the bar of his restaurant when I arrived. I was surprised to find that Stitt was slight and rather soft-spoken; with his formidable reputation, I'd imagined him to be much more imposing. He, looked, well, sort of French. He was not only happy to talk about wine, he was positively euphoric. "One of the great qualities of wine is that it is intellectualism combined with hedonism," he opined, then happily enumerated some of his favorites: "I love wines of the Rhône, the Loire Valley and, of course, Burgundy, especially Chablis," he said. In fact, Stitt noted, François Raveneau, the Chablis producer that can command up to $1,000 a bottle, once made the Highlands house white. "Not Chablis, but a nice Bourgogne Blanc. We sold it for $9 a glass." He listed a few other wines he loved—FX Pichler Riesling, the Burgundian-style wines of Josh Jensen of California's Calera. "Basically, I love wines with acidity," Stitt said. "They're the kind of wines that are very important to me as a cook." Wines with acidity and a touch of obscurity clearly had a place on Stitt's lists.

When I asked him why he no longer employed a sommelier, Stitt told me that he relied on his waiters to sell the wines. And yet I couldn't help thinking that the complexity of the wines he had chosen, not to mention the caliber of his restaurants, warranted the services and attention of a sommelier—someone who could guide diners though the list and explain why certain pairings worked and others might not. And of course, it would be great to have someone to inform customers with an interest in Chablis that they would do well to drink up all the bargain-priced Raveneau. The wine choices here showed a true discernment that I felt deserved deeper explanation than a busy waiter could deliver.

I considered all this the next morning as I drove once again to Birmingham's suburbs, this time to check out the grocery stores I'd been told had great wine selections. Western Supermarket, in Mountain Brook, employed a wine staff of three who took turns answering questions from nine in the morning until seven at night. When I arrived just after nine, I found wine consultant Scott Atkinson answering a customer's question about a Pinot Noir. The man couldn't remember the name of the wine, only the label. Atkinson took him patiently shelf by shelf, bottle by bottle, trying to jog his visual memory.

The store selection was broad and diverse, from "regulars" like the Chocolate Block and Château de Beaucastel to cultish wines like Robert Foley Vineyards Charbono, Switchback Ridge Petite Sirah, even a Cassis Blanc from the tiny Provençal producer Clos Ste. Magdeleine. There was a nice Chablis section and Grüner Veltliners from star producers like Weingut Hiedler and Schloss Goblesburg. "We're selling a lot of Grüner Veltliner," Atkinson said.

The selection was also quite good at the Piggly Wiggly supermarket a mile or so away, but it was the store's 28-year-old wine director, Andrew Brim, who impressed me the most. Articulate and lively, Brim had worked for Stitt for three years as a waiter before taking his grocery-store job. He was a big Stitt fan. In fact, according to Brim, "You can trace Birmingham's wine expansion directly to Frank." Not to mention a lot of Brim's own retail sales. "I can see a direct correlation between what Frank is selling by the glass and what we are selling in our store. His house Adami Prosecco is one of our best-selling wines." The supermarket's selection, Brim said, was a delicate balance between Stitt's favorites, commercial wines like Yellow Tail and wines Brim himself loved. He pointed out a few of his favorite finds, like Washington producer Charles Smith's wines. "His Boom Boom! Syrah is terrific."

Brim didn't think Birmingham was "ready" for a sommelier yet. "People going to restaurants here just don't want to pay for a sommelier. Maybe in the next decade," he opined. The next decade? Would Birmingham really have to wait that long? What about Brim—would he take on the job? "Then I'd have to work weekends and nights," he said with a smile.

On my way back to New York, I considered the puzzle that was Birmingham. There was great food in its best restaurants but unexciting wine choices—except at Frank Stitt's places, where there was terrific food and interesting wine, but no expert to put the two together. There were wine directors in town, both willing and knowledgeable, but they were all in grocery stores.

Perhaps, I thought, Birmingham's former sommelier might have some insight into the matter. I tracked down Sean Meyer in Napa, mere minutes before he was to take his Master Sommelier exam. After leaving Birmingham, Meyer had gone to work for Jess Jackson as sommelier and wine educator for Jackson's Artisans & Estates wineries.

So why wasn't there a sommelier in Birmingham? Meyer posited that it might also be money. "The margins on wine prices in Alabama are much smaller than they are in places like New York," he explained. "That's good for wine drinkers but bad for restaurateurs, since it means lower profits."

I had an idea. If it was money that was keeping Birmingham's restaurateurs from employing a full-time wine professional, why not employ a sommelier who could rotate from place to place and split the cost? After all, the four Frank Stitt restaurants and the Hot and Hot Fish Club are all within a few blocks of each other, and Café Dupont is only 20 blocks away. They share many of the same food purveyors and farmers; why not the same sommelier? Maybe they could hire one of the grocery-store wine directors. Birmingham could make history by introducing the first sommelier time-share.

If not, well, I suppose I'd urge all Birmingham diners (or out-of-towners like me) to visit a grocery store and BYOB at a restaurant (according to Chris Hastings, the corkage fee at Hot and Hot is just $15). Perhaps they'll want to check out Andrew Brim's selection at the Piggly Wiggly in Mountain Brook—and buy a bottle of what Frank Stitt is pouring by the glass.