It had been eleven years since Vieira had played the Baía das Gatas festival. Was it good to be back in Mindelo? "I don't like to think of the old days—of Cesária," said Vieira, who piloted her early albums but who has had a long-running feud with the Barefoot Diva and the owner of her record label, José da Silva. "I treated her like a baby learning to walk. Then Cesária had a little success, and José da Silva would promote only her. He wouldn't let anyone else succeed. Decades ago, I loved helping people remember our traditions," he went on, staring into the palm of his hand. "But I became frustrated. I didn't feel like I was needed here."

We'd been talking for an hour when we heard music. Morgadinho, one of the founding members of Voz De Cabo Verde, was playing in the hotel's terrace lounge. Morgadinho and his quintet had just wrapped a song when he saw Vieira walk in. Morgadinho directed the packed room's attention to the man attempting to hide behind a pole. Applause erupted. Vieira nodded bashfully, and then, feeling appreciated, he smiled. "Come on," he said, as he sat down at a table full of friends. "Let's have some drinks!"

I was still in the headlock of Cape Verde's national liquor—a sugarcane-based rocket fuel called grogue—as I wobbled up the gangplank of the Mar d'Canal the next morning. The 8 a.m. ferry was headed for Santo Antão, Cape Verde's second-largest island and the one with the country's highest rainfall (Cesária calls it "the promised garden"). Waiting for me in the main town of Porto Novo was Norberto Santos, a basketball-loving father of five who'd learned English as a teenager in Rhode Island. Getting into a four-by-four, we began the long climb toward Cova de Paúl, a dormant volcanic crater. The air was moist and cool. Pine trees began to appear. Had we been tele-transported to Switzerland?

There are few sandy beaches on Santo Antão, but the hiking trails go on and on. We chose one that started at água das Caldeiras and descended into a wide green gorge called Ribeira do Paúl. The cobblestoned path would have impressed the Incas. Even more marvelous was the valley's series of shallow, stepped terraces thick with figs, guavas, peppers, and manioc.

Back in the four-by-four, we reached the coastal village of Vila das Pombas three hours later, where we stopped at a grogue distillery that still uses oxen to turn its sugarcane press, or trapiche, reputed to be four hundred years old. I bought a few bottles each of grogue and a sweetened version, called ponche. From there, we continued on along the island's northeast coast, past what's left of the village of Sinagoga, where you can find the graves of Portuguese Jews who sought refuge here in the nineteenth century, along with the ruins of a leper colony on the beach.

Eventually, the road led to a happier place: Ponta do Sol, a pastel-painted seaside town where you can rent mountain bikes and scuba gear. After lunch (tuna with pesto made of a lemongrass-like herb), we drove back toward the ferry. As we scaled the spine of the island's mountain range, which rises to some five thousand feet, the car suddenly entered a cloud. Mist spilled across the road like suds out of a washing machine as we inched our way along the switchbacks. From time to time, the fog would part to reveal a girl waiting for a bus... two donkeys with gleaming eyes... a boy who turned out to be a hunched old man. It was like motoring through the subconscious.