Ever since the 1400s, when Basque seamen first voyaged here for cod, seafood has been a lure. The briny marine air hits you upon arrival. So does the cold. When my plane landed at Saint-Pierre's airport last August, the temperature was 48 degrees Fahrenheit. Hence the local expression l'hiver est venu passer l'été—winter has come to spend the summer.

No one I knew had ever spent a day here. France's remaining bastion in North America is something of a mystery. Scant information is available online or in books about Saint-Pierre (population: 5,676) and its sibling Miquelon (635 inhabitants). Geographically Canadian, the territory is administratively European. Passports are stamped by French customs officials. The currency is the euro. In Saint-Pierre, the main port of call, old men play pétanque and drink pastis in the square.

Like explorer John Cabot, who stumbled onto the archipelago while searching for Cathay in 1497, I'd come in the spirit of discovery. My goal? Seafood. Saint-Pierre and Miquelon's official motto is a mare labor, a Latin phrase meaning "from the sea, work." I intended to work my way through the bounty.

My first stop, at my taxi driver's suggestion, was a diner by the improbable name of Café Cyber Poly Gone Home. The lanky chef Philippe Pupier served me a traboulette—country bread slathered in béchamel, topped with Puy lentils, saucisson, and Gruyère—and chatted with me about local dishes: tiaude, a thick fishermen's stew of potatoes, carrots, and cod; and_ boulettes de morue_, salt cod fritters, known here as "cod snowballs." These traditional foods, he said, are hard to find outside of home kitchens, but he'd prepare a menu of classics during my visit. I had to leave for Miquelon the following morning—there was a local seafood festival there that I didn't want to miss—but we agreed to reconvene upon my return.

The next day I awoke to a landscape enshrouded in milky brume. The hour-long ferry to Miquelon left at dawn. “You can't see the sky from the sea,” said the ship's captain, smiling as he navigated by GPS. The atmospheric gauze would blow off before noon, he assured me, steering over wine-dark waves into the vaporous nothingness.

Hours into my visit to Miquelon, the mist remained as thick as brandade. Wild horses grazing on the strand looked like washed-out ghosts. I was trying to imagine how hard it must be to fish these waters when an aroma of charring seafood speared through the gloom. The smokiness seemed suffused with hints of violets and cucumbers. "What is that?" I said out loud. A white sky withheld any clues, so I set off in blind pursuit.

I ended up in front of my B&B, where the owner, Paulette Boissel, had greeted me earlier with “Bienvenue! We're the exiles at the ends of the earth.” About to give up on the beguiling perfume, I noticed a neighbor sitting on his stoop beside a cast-iron plate mounted on a flame-emitting gas canister. It held a dozen small silvery fish.

“These are capelins grilled à la plaque—and they're nearly ready!” the man, named Loic, told me when I approached him. During the spawning season, the ocean boils over with these smelts, historically food for cod and other big Grand Banks fish. You can reach a pail into the water and pull them out by the dozens. Their flesh has a surprising floral aroma, he said.

These had an added pungency from the way they were cured. Loic sun-dries the small fish and then brines them in salt in the backyard. He invited me inside, where his wife, Natalie, and their children were spreading butter on bread. “You can't have capelins without bread and butter,” Natalie declared.

“And you can't have afternoon tea without capelins,” Loic added. The inhabitants of Miquelon always have afternoon tea at 4 p.m.

“Everybody gets peckish around this time,” Natalie explained. “You'll join us for tea, bien sûr?”

The capelins were as delicious as they smelled: toothsome, saline, grill-blistered. The butter offset their minerality perfectly. Traditional recipes are simple, Natalie said. The never-ending winters had taught residents to do a lot with a little. A staple is salted cod, although it's increasingly hard to come by—the cod fisheries collapsed more than two decades ago. But there is still life in the sea. And the best place to sample it, she said, would be the seafood festival the following day. For this elaborate potluck, everyone prepares their best recipes. The owner of my pension, for instance, would be bringing her famous mussel tart.

Thanking Loic and Natalie, I went to check in on Paulette, who was indeed cooking her trademark dish. With her short white hair, nurselike apron, and silent sailor husband, Paulette was as tough as oyster shells but in a humorous way. She told me that most of the island's population could be traced to the Basque Country, Normandy, or Brittany. “Me, I'm Basquaise,” she declared, toothpick dangling gangster-moll-like, fists raised as though to say, “Come on! Any takers? Who wants to go?”

Paulette had made enough tarts to spare one for her houseguest. It turned out to be supremely satisfying, the pâte brisée shell blanketed in mussels and a creamy mornay sauce. Afterward, hoping to walk off my rich snack, I moseyed down to the wharf to scope the catch. Twilight descended and mariners, faces chiseled by the wind, started motoring into port.

“Were they biting?” I asked.

“There's nothing out there tonight,” said a large, ruddy-cheeked man in rubber boots, gruffly.

“But when you actually catch some encornets,” he continued, using the local term for squid, “you grill them or stuff them.” He'd caught bucketloads at dawn and was planning to stuff them with bread crumbs and aromatics for the next day's buffet.

“Could I come and see?” I asked. He looked me up and down and then told me to jump in the back of his pickup.

At his house, the man, named Jean Maurice, fired up a metal plaque similar to Loic's and grilled some squid plain, explaining that superfresh encornets don't need seasoning. When heated, their ink forms a natural sauce that complements the squid's seared exterior sumptuously. Then Jean Maurice, employed as captain of a scallop barge, suggested that his wife, Carole, whip up her specialty, coquilles St-Jacques—scallops au gratin.

I protested because I was exceedingly full. “That's about right,” said Carole, who makes fantastic scallops. “Everybody here has four o'clock tea, then an apéro at 6 p.m., and then dinner at 8 p.m., so you're on track.”

They also have three meals before that: breakfast, a midmorning snack, and lunch. “Le monde adore manger ici,” as Paulette had said—“people love to eat here.”

The next day I went to rent a bicycle and explore the island. The bikes all needed repairs, the young shopkeeper said. But if I wanted, her dad would give me a tour. Minutes later, a kindly gentleman drove up and introduced himself as Denis Detcheverry. It turned out he was Miquelon's former mayor and currently the local senator. He spent part of each year representing the islands in Paris. “Our cuisine is French, with our own touches based on nature's offerings,” he said, pointing out streams full of trout. Locals eat seasonally by necessity, he explained. Fall and winter is the time for cod, deer, wild hare. Spring brings the best sea urchins. In summer forests are blanketed with chanterelles and fields with wild strawberries.

It had been at least an hour since my last meal, so Detcheverry suggested I come over for lobster. After he parked, I went down the street to pick up a bottle of wine and returned with a white Graves from Clos Floridène. “They have fantastic wines at that grocery store,” I remarked.

“Of course they do. We're in France after all,” he replied.

He cut the lobsters in half lengthwise and grilled them_ à la Normandie_ with splashes of calvados. The wood fire's smoky essence fused seamlessly into sweet flesh accentuated by notes of cooked apples. It whet my appetite for more, so I left Detcheverry and joined the people streaming through the foggy streets to the seafood festival, which was starting in a sports gymnasium three blocks away.

Despite the gloomy weather, it was cheery in the gym. Each home cook had contributed to the buffet: lobster mousse, tuna pâté, cod fritters. Shrimp and snow crab were stuffed into every hollow: halved peaches and tomatoes, hard-boiled eggs, coils of smoked salmon. Lobsters with pincers like baseball mitts encircled asparagus-crowned crab spreads and trout in aspic. At the sound of a whistle, participants stampeded the gargantuan spread.

“This is very old, real, roots France,” one visitor from Paris exclaimed. “It's like something you'd find in the backwoods of Auvergne or Limousin. This feels like the most out-there place that's actually inhabited.”

People started dancing, young and old alike. Hours later, everyone trickled out, full and happy. Having feasted hard, I slept peacefully amid the Bonne Cuisine books and trophy antlers that graced the shelves at Paulette's.

In the morning, the sky above the ferry back to Saint-Pierre was less overcast. Jagged cliffs wavered in the distance; seabirds rippled the waters with their wingtips. I landed and headed for the portside diner. Philippe Pupier was blasting Maria Callas on the sound system when I arrived. As promised, he had made a meal for me. It started with tiaude, which was gloriously direct: cod cheeks and vegetables in a thick roux. Then, tender chunks of bisque-moistened lobster were served en croûte, in mini cocottes sealed with puff pastry. And cod snowballs, creamy with a crisp golden exterior. Made from island recipes, it was a wonderful lunch, as good as any I would have had at a fine bistro in Paris. Yet here we were nestled away in a tiny fishing village just south of Newfoundland in the fog thickets of nowhere, a place where they live to eat.