There are destination restaurants, out-of-the-way and often overpriced fine-dining joints run by celebrity chefs who attract limos full of foodies and their followers.

Then there is Sa Foradada.

It supposedly had some of the best paella in Mallorca, Spain's largest island. And my wife and I were determined to try it on a recent trip.

But the tiny, rustic eatery clings to a wind-swept, rocky promontory jutting into the western Mediterranean, a site so remote that you can only reach it by sea or on foot.

We tried booking a water taxi from Port de Sóller, about five miles up the coast. It was supposed to drop us at a secluded cove where we could climb steep stone stairs to the restaurant. But the captain decided the seas were too rough, and he again canceled when we retried three days later.

So we hiked in. We had been told to climb over a metal gate off a side road at Son Marroig, the former estate of an Austrian archduke, to find the unmarked trail. From there, we zigzagged down a mountain track for nearly an hour, through terraces of gnarled olive trees and lush pines, and onto a narrow rocky spit flanked by crashing surf.

We finally reached what looked like a shack on a cliff. Just below it, a chain with a red stop sign blocked the path. A woman dressed in black appeared. "Do you have a reservation?" she asked pleasantly.

We did, and we were given a table along the rail, overlooking the turquoise sea. Sunlight dappled through a roof of matted reeds. A jagged precipice across the cove was pierced by a natural hole, like a dragon's eye, the forat in the local Catalan dialect that gives the hole-in-the-wall restaurant its name.

We ordered a pitcher of sangria with cava, Spanish sparkling wine, and settled in for an extraordinary three-hour lunch.

We had come to Mallorca to visit friends at their graceful seaside villa in Portopetro, on the southeast coast. The quiet fishing village seemed a perfect bolt-hole in the second autumn of the pandemic. The health agency for Mallorca and the other Balearic Islands claims more than 80 percent of the eligible population is vaccinated against the coronavirus. And Spain's restrictions are so tight for foreign visitors that we almost didn't get in.

"I can't go," my wife had declared after she tried to check in online the day before our flight to Madrid. "They won't accept my name."

The problem was that her U.S. passport was in her maiden name, while her vaccination records showed her married name. Because they didn't match, the Spanish online health portal wouldn't issue her the QR code required to board the flight or enter the country.

A day of increasingly frantic calls and emails to health agencies and government offices led nowhere. Then the Spanish consulate sent an unsigned email suggesting we try our luck at the airport.

At the Iberia counter, a very patient ticket agent spent more than an hour reviewing our documents, consulting her supervisors and tweaking the app until the QR code magically appeared on my wife's phone.

We had to show that QR code at four checkpoints after we landed in Palma, Mallorca's largest city. And every restaurant, shop and other indoor site we entered during our two-week stay required masks. I rarely saw anyone defy the rules.

Mallorca is best known as a playground for the super-rich, and a local English-language website, the Majorca Daily Bulletin, did not disappoint in its coverage. Headlines announced that Prince Albert of Monaco had arrived, as had the "world's most avant-garde super yacht."

However, mostly German and English tourists flock here. They are the latest in a very long line of foreign invaders: the Phoenicians came in around 8th century B.C., followed by Roman legions, marauding Vandals, Moors, Ottoman Turks and others.

With so much history, and 1,400 square miles, there's lots to see.

Barbary corsairs built coastal watchtowers in the 17th century that still flank several harbors. We walked across the Pont Romà, an arched stone bridge in Pollença that the Romans built 2,000 or so years ago and is still in use.

In Palma, we admired the immense Cathedral of Santa Maria, which dates to the 13th century and is one of the tallest Gothic structures in Europe. The honey-colored basilica, which took 400 years to build (and was rebuilt after an earthquake in 1851), was erected over a Moorish mosque, which itself sat on a Roman fortification.

Today, La Seu, as the cathedral is known, looms over Palma's Old Town, a busy warren of handicraft shops, tapas bars, historic palacios and sunny plazas. After wandering the cobbled streets one morning, we ducked into the Mercat de l'Olivar, a vast indoor food market, and found high-table seats at Ostras, one of the stalls along the wall.

Soon we were gorging on heaping plates of grilled razor clams, cockles, octopus with potatoes, shrimp, and more. The bill for three, including a bottle of cava, was $98.

One could fashion a tour to Mallorca just to visit the ancient windmills, the terraced vineyards (Pliny the Elder, who wrote extensively about wine in the 1st century, was a big fan of Mallorca's terroir), the countless fairs and festivals, or even the many lighthouses, including one in Portopí that was built seven centuries ago and is still working.

Late one afternoon, we drove up to one of Mallorca's best-known monasteries, the Sanctuary of Sant Salvador. It was built atop a mountain during the Black Death, the 14th-century pandemic that wiped out much of Europe's population, when friars believed the cool air at about 1,500 feet would keep the plague at bay. It didn't. But the views are breathtaking.

Beaches are a big draw on Mallorca, although be forewarned: In many places, that means spreading your towel on stones or slabs of rock, not sand. But Moorish-style manors, with horseshoe arches and keyhole windows, often sit beside boxy, white, Bauhaus-inspired villas on the coastal escarpment, so the discomfort is probably worth it.

We spent most of our second week hiking the rugged trails and visiting the medieval villages tucked under the craggy cliffs and jagged ridges of the Serra de Tramuntana in northwest Mallorca. UNESCO has listed the mountains as a World Heritage site, like Yellowstone National Park.

The Tramuntana are especially known for their drive-if-you-dare roads. So, early one morning, we jumped in our rented Audi and headed for the village of Sa Calobra, the endpoint of one of those only-in-Europe, impossibly serpentine roads with loopy, hairpin turns and crazy S-curves on vertiginous cliffs by the sea.

"Bond. James Bond," I announced as we whipped around the first dizzying switchback. Then another. And another. We dodged bicyclists, oncoming cars and the odd goat for more than an hour on the wild, winding road. Then, to my amazement, a tiny red Fiat passed me, buzzing by before disappearing around a blind turn. I realized I was driving so slowly, I was blocking traffic. My ego quickly deflated.

At the bottom, we parked and walked down to the Bar Playa La Calobra, one of several seaside cafes in the tiny settlement. We grabbed a table on the veranda and ordered restorative cortados and apple cake. My ears perked up when the tinny sound system played the theme from "Mission: Impossible." I felt better.

A nearby path led to two dimly lit tunnels carved through solid rock and out to a small, pebbly beach. Families and couples sunned on blankets or swam in the tiny cove that once sheltered smugglers and pirates. We instead shouldered our day packs and began hiking up a deep canyon known as the Torrent de Pareis.

The gorge is subject to dangerous flash floods when it rains, but the sky thankfully was clear. Steep limestone walls, sculpted by wind and water into twisted cracks and grottoes, soared hundreds of feet high as we clambered over, under or around huge boulders. Swallows wheeled in and out of the shadows.

After 90 minutes or so, we met three college-age hikers scrambling down. How far to the top, we asked. About four hours, one said. And 2,200 feet up, the second said.

"You'll need ropes," the third added helpfully.

We did not have ropes. Or four hours. We settled for the picnic we had brought along - paper-thin slices of salty-sweet Ibérico ham on fresh dark bread - and turned back.

Which brings me to our lunch at Sa Foradada.

Our table - one of 25 on two terraces - offered a clear view of the open-air kitchen. We watched cooks juggle blackened pans of simmering paella and other dishes on a forge-like grill set over a blazing wood fire.

It was a reminder of the dish's humble origins. Back in the early 1800s, farmworkers near Valencia used a shallow pan to cook short-grained rice (the Moors first planted the grain in Spain) over wood fires, tossing in any ingredients they could find, for a filling one-dish lunch.

Today, paella - the word is from patella, or small pan, in Latin - is arguably Spain's best-known culinary export. Yet the precise ingredients, and how they should be cooked, are hotly disputed.

Valencians insist their calcium-rich water is required to flavor the stubby rice. Fans farther north in Barcelona covet the socarrat, the crunchy dry crust that forms on the rice after all the water has evaporated.

Some aficionados demand mussels, clams, squid and shrimp. Others prefer chicken, rabbit, pork and snails, citing paella's peasant roots. Peas or no peas? Spicy chorizo and crayfish have been known to join the mix.

They all sounded pretty good to me.

So after diving into grilled red shrimp and a salad as starters, we decided on the mixed paella: saffron-flavored rice with seafood, vegetables and meat cooked over a sofrito, or flavor base, of garlic, onions, tomatoes and peppers.

After 45 minutes or so, the waiter brought a steaming pan to our table and spooned the golden-hued mixture onto our plates. That's another no-no in some parts of Spain, where it's said paella must be eaten straight from the pan.

The dish was rich, smoky and dense with flavor, unlike any paella I had eaten before. A salty breeze from the sea only enhanced the taste. We topped off with fresh-baked coconut carrot cake to fortify ourselves for the two-mile uphill hike back.

After paying the $126 bill, I approached the manager and chief chef, Lidia Fernández Morell. We chatted under dangling ropes of garlic and peppers as she garnished five pans of paella, flipped a grilled dorado and stirred two huge pots of seafood stock, all while feeding pine boughs into the fire.

Her parents, Emilio and Magdalena Fernández, began cooking paella on the cliffs in the 1970s, she told me, and steadily built the business despite the desolate site.

Now, she and her sister supervise a staff of 10, serving lunch six days a week from April to October. (It closed for most of 2020 because of the pandemic and only opened in late July this year.) Reservations are recommended two weeks ahead in summer, and hike-ins are often turned away.

I said I was pleased her paella didn't have a socarrat crust on the bottom, because I find the taste bitter. "We can make it, but people here don't like it," the chef agreed.

So is it the best paella in Mallorca, I asked. "People say so," the chef said with a shrug. "I don't know."

Nor do I. But it hardly mattered. The experience was sublime.

- - -

IF YOU GO

Where to Eat

Sa Foradada

Crta. Valldemossa, Deià, Km. 6

011-34-616-08-74-99

restaurantesaforadada.com

You can only reach this small cliffside restaurant by hiking down a rocky mountain track or hiring a boat from Port de Sóller. Either way, it's worth the trouble. Chef Lidia Fernández Morell cooks world-class paellas on a wood fire; fresh fish and other local fare are also available. Lunch only, and reservations are highly recommended. Paella about $26 per person.

Ostras

Plaça de l'Olivar, 2, Palma

011-34-637-70-54-72

Deep inside the Mercat de l'Olivar, a vast indoor food market, this busy seafood stall is a hidden gem. Sit at the high tables, order a glass of cava or champagne, and tuck into the morning's haul of shrimp, octopus, cockles, oysters, razor clams and more. No reservations, and there's often a line. It's worth the wait. Lunch only. Tapas-size portions from around $10.

La Posada

Calle Mirador de Lladoners, Local 6, Valldemossa

011-34-630-97-87-00

Grab one of the small tables on the upstairs balcony and enjoy the view of the red-tiled roofs and spires of a medieval town tucked into the rugged Serra de Tramuntana mountains. The tapas are as good as the scenery. We dove into shrimp with garlic, octopus Gallega-style, meatballs and spicy potatoes. Open for lunch and dinner. Tapas from around $9 each; a full menu is also available.

Bona Taula

Carrer Rafel Adrover, 3, Calonge

011-34-971-16-71-47

restaurantbonataula@gmail.com

Locals are so loyal to this rustic restaurant in southeast Mallorca that the walls feature numerous photos of patrons who return year after year. Most diners head for the 40 seats in the back garden, where the tables nestle under leafy grape arbors. Those inside can watch chefs grill rabbit, duck, entrecôte beef and more on a wood fire. Or try the amazing suckling pig. Dinner only. Entrees from about $15.

What to do

Cathedral of Santa Maria

Plaça de la Seu, s/n, Palma

011-34-971-71-31-33

catedraldemallorca.org/en

This massive Gothic cathedral, known to locals as La Seu, has ornate spires and buttresses that still dominate the Old City of Palma. It's worth the entrance fee to see the 61 stained-glass windows, which flood the interior with shafts of colored light. Includes a small museum. About $9 for a general ticket for a cathedral visit and an audio guide, about $8 for those older than 65. Worshipers get in free.

Frédéric Chopin and George Sand Museum

Real Cartuja de Valldemossa Plaza Cartuja 9, Valldemossa

011-34-971-61-20-91

celdadechopin.es

The famed Polish composer and his French lover, a novelist known by her male pen name, spent the winter of 1838 at this former Carthusian monastery in Valldemossa. When he wasn't complaining about the rain and the food, Chopin composed his Op. 28 Preludes on a local piano. His own Pleyel upright was impounded by customs, then hauled by donkey over the mountains, finally arriving shortly before he left Mallorca. It's now on display with letters, drawings and other memorabilia. Tickets about $6 adults, about $3 for children under 10.

Sa Calobra

abc-mallorca.com/sa-calobra

Getting here is more than half the fun. The eight-mile mountain road features seemingly countless hairpin turns carved into pine forests and steep crags, offering stunning views. Cyclists come from around the world to try it. At the bottom lies a tiny seaside village with paid parking. A footpath takes you through two dimly lit tunnels and onto a gorgeous beach tucked between two cliffs. Bring your own towels and everything else. There are no lifeguards. A challenging hiking trail behind the beach leads up the Torrent de Pareis canyon.

Cap de Formentor

bit.ly/CapDeFormentor

Drive the winding mountain road that climbs, switchback by switchback, to the lonely lighthouse at Cap de Formentor, the northern tip of Mallorca. It may as well be the end of the world. The approximately 12-mile road from Port de Pollença twists and turns, often with jagged cliffs on one side and thrashing surf far below, but the views are spectacular. There's a small cafe at the lighthouse. Free.

Information

mallorca.org/en