The mal refers to heartsickness, as in the feeling of missing Africa. For Sicilians, mal d'Africa is a kind of phantom continent syndrome, a sense of nostalgia for a lost homeland, a homesick longing for the landmass next-door that played such an important role in shaping their way of life. We all have it in some way, that desire to return to an impossible elsewhere. But people here speak of having mal d'Africa when they've been traveling away from home for too long. They miss Africa; they need to get back to Sicily.

On the morning I arrive, everything outside the airplane's window is frosted in white clouds. From the lemon gelato sky, I descend into Palermo, a honking, city-sized souk lined with palm trees, closer to Tunis than Naples. When the campanile rings at the city's main cathedral (its architecture Arab-Islamic, Byzantine-Orthodox, and Norman-Catholic), it sounds more like interstellar gamelan music played on gongs than Continental church bells.

Shaking off the jet lag, I refuel on a freshly squeezed orange spremuta from a small café in the heart of the Ballarò street market, a lively, semi-chaotic bazaar that has animated Palermo's daily life for more than a millennium. Much is on offer here (obsolete electronics, bootleg perfume), but the real draw is the produce. Glossy black olives as big as plums sit next to giant preserved lemons and tubs of glowing red harissa. Piles of long and skinny cucuzza zucchini are stacked on top of their leafy tendrils, ready to be transformed into minestra. Raisins and pine nuts come packaged together for convenience, as so many Sicilian dishes combine them anyway.

On one street corner, a guy is hawking five kinds of eggplant. "La caponata!" he shouts into the morning air. We strike up a broken Italo-English chat in which he informs me that eggplants were first imported into Europe via Arabs who ruled Sicily a thousand years ago—and that the combination of sweetness and acidity that goes into a caponata is itself a hallmark of the Arab-Sicilian touch. "Agrodolce," he says, sending me off with a pat on the back before continuing to holler at passersby.

A few other vendors are pepper-spraying the atmosphere with their abbanniate, their stentorian cries, using the venerable Palermitan method of selling-by-yelling. A Falstaffian fellow bellows "Babbalucci!" over and over. Sicilian for snails (as opposed to chiocciole or lumache on the mainland), it's a euphonious word that is believed to be derived from the Arabic.

These babbalucci are sold alive in immense squirming mounds, their shells clinking together like delicate castanets as they spill out of their crates. When I ask the snail man how to eat them, he puts his garlicky fingers to his lips and makes a loud kissing sound. "Baci!" he adds, laughing uproariously, making sure I understand that the Sicilian way is to smooch the snails right out of their shells.

I stop for some cornetti at a popular stand. The owner assures me that her cornetti filled with pistachio cream aren't just molto buono, but that they are, in fact, "crazy amaze-y." Why is that, I inquire? Because they use pistachios from Bronte, the veritable Città del Pistacchio on Mount Etna. Pistachios are yet another treasure brought to Sicily when it was under Islamic rule, and the filling puts an interesting twist on the old tale that croissants were made to resemble the Ottoman crescent moon.

Nearby stalls sell pannelle di ceci (Arab-style flat chickpea flour fritters) as well as arancini, those well-known bread crumb-battered and fried rice balls whose original recipe is said to date back to the tenth-century Kalbid dynasty.

It doesn't take long to feel deeply steeped in the general North Africanness of this place—especially if that's what you've come looking for. This is an expedition I'd been hoping to do for years. It began, as these sorts of things do, in a tangential way. Skimming through an encyclopedic tome about the history of gastronomy in Quebec, where I'm from, I happened across a passage suggesting that French Canadian cuisine has its roots in the Muslim food of ninth-century Italy. Sicily was then central to Arab life in the Mediterranean, the conjunction of East and West, North and South, Africa and Europe.

Muslim settlers introduced Italy to the durum wheat they could use for pasta, to rice for risotto, and to sugarcane for dolci. Citrus fruit, spinach, chickpeas, artichokes, and sesame seeds—all of them, plus eggplants for caponata and myriad other ingredients, were brought to Sicily from North Africa. Arabs overhauled their colony with new systems of agriculture, using terrace cultivation and siphon aqueducts for irrigation. These, together with their agrodolces and arancini and world-remaking cooking techniques, gifted this land with what's sometimes known as cucina Arabo-Siculo.

Several excellent books by Mary Taylor Simeti and Clifford Wright explore the subject of Arab contributions to the cuisine, but they were published in the late '80s or '90s. A lot can change in 25 years. How evident is the North African connection now? Can the layers of influence still be disentangled? Can traces of the ancient even be isolated in the flavors of modern Sicily? I intend to spend the next week finding out by driving around the island in search of surviving connections.

My guide for this mission is Marco Scapagnini, who presently screeches up in his Ford Galaxy SUV. Scapagnini, a scruffy, jangle-nerved, 43-year-old with a charming, devious smile, is a journalist, guidebook writer, and proprietor of a tour company called NicheItaly. Despite the many niches he's explored, he's never set off in search of evidence of North Africa's enduring culinary influence, and he's as curious as I am about what we'll find.

Our itinerary calls for us hitting a different town every day: The plan is to head first to Erice—a mountainous fortress in the sky—then down the western coast and along the south all the way to Siracusa. We'll end up on the slopes of Mount Etna in the pistachio wonderland of Bronte before circling back to Palermo along the northern coast. It's an ambitious circuit: Sicily is bigger than it looks on the airplane's seat-back screen. I'm confident knowing that a seasoned local is driving, though our trip begins on a wobbly note when Scapagnini immediately reverses into a fountain or a public sculpture or some large container of some sort outside the market. I can't tell what it is because he drives off without getting out to check the damage. “It was just a vase, for palm trees,” he reassures me, as we lurch away from Palermo.

The town of Erice is an hour-and-a-half drive without traffic. Unfortunately, there's always traffic; it's rumored that the roads are maintained in such pitiable condition by the Mafia. They could take some cues from the Phoenicians, who used to rule this part of the island, as some of their stone walls—built at the time of the Punic wars—still stand around Erice. The town itself, perched atop a cliff, is perfectly situated for protection against invasion. The way up is a steep, winding, cobblestone path that we decide to tackle by foot. (There's also a cable car to the summit.)

The trek is absolutely worth it: Near the top, we come to the greatest pasticceria on Heaven or Earth. Since 1963, the former nun Maria Grammatico has been running this world-famous pastry emporium, specializing in mind-blowing almond-based confections made using ancient recipes from nearby San Carlo convent, where she was cloistered in her youth.

Today she runs her busy shop like an iron-fisted despot, with a squadron of employees scurrying around in a state of permanent trepidation. I tell Marco that she seems like an empress, the conquering pastry sovereign of Erice. He nods. “She's tough, and she can be a bit rude,” he confides. “But she treats me like a grandson. And she gives me excellent relationship advice.”

Before we get into details of his romantic life, our attention is diverted to a platter of specialties. I would have imagined that the thing to have here must be the cannoli; this is Sicily, after all. And they are, in fact, incredible—the ricotta both super fresh and not overly sweetened, the ends dusted with chopped pistachios from Bronte—possibly the only truly great cannoli I've ever eaten.

"Now try the real things," Grammatico mutters, unveiling a tray laden with frosted green ping-pong-ball-sized pistachio-rum orbs. They're deliriously good, and my teeth instantly feel like they're shellacked in icing sugar. Up next are puffy, custard-cream disks called genovesi, followed by a platter of sweet biscuits that Grammatico says used to be called "nun's breasts," as well as some small, dome-shaped almond-and-egg-white cookies called sospiri, or sighs. "These are the amazing almond pastries she learned to make in the convent," Scapagnini tells me, sighing.

Grammatico shushes him and says that the only secret is using the right almonds—bitter almonds from Avola. “They are the best almonds in the world,” she adds, looking at me like she has never uttered anything more important in her entire life.

“And how did they get to Sicily?” I ask.

“Arabs brought them,” she answers, without hesitating and without changing that exquisitely serious facial expression.

As I sit there, taking notes, Grammatico starts dispensing grandmotherly relationship advice to Scapagnini. “She's telling me that the way to conquer a Sicilian girl is to be persistent and not give up,” he says, filling me in. “Maria is always right.”

“So you're in love with a Sicilian girl right now?”

"I'm always in love with a Sicilian girl," he replies.

I'm coming down from my pastry high by the time we reach our next destination, Firriato Winery, which operates a swanky resort in the hills of Trapani, a picturesque seaside town where people eat anchovies al fresco in front of beautiful, dilapidated, baroque buildings on old cobblestoned streets. Property manager Alberto Oliviero, a bald Marlon Brando lookalike with an extremely calm demeanor, joins us at the winery's lookout to take in the sunset. He's so Zen that merely being in his presence feels like attending a meditation retreat.

The question of where to go for dinner comes up. Oliviero ponders this for a few languid moments, taking a sip of white wine. “Hostaria San Pietro,” he whispers, finally, in his smoky, soft-as-incense voice. “It's one of my favorite restaurants in Trapani.”

When we arrive, at the stroke of midnight on a Wednesday, the place is utterly jam-packed. People are eating at makeshift tables that have been set up in the crowded parking lot outside. We get placed at the end of a long, plastic-covered table next to some extremely happy Sicilians. Hostaria San Pietro doesn't bill itself as anything other than a Sicilian restaurant, but the food tastes distinctly North African. The Tunisian-born chef Fadaoui Badreddine starts us off with an antipasto misto served on lovely hand-painted plates. We devour a perfect caponata, its zingy celery-and-pine-nut-spiked agrodolce undertones giving the eggplant a tastebud-spanking raciness. Just as satisfying are Badreddine's peperoni con la mollica (roasted red and yellow peppers in bread crumbs), his plump cubelets of cured mackerel, and his cipollata di tonno (tuna with onion). My favorite, however, is the baby cuttlefish in a cherry tomato sauce thickened with its own ink and leavened with flashes of harissa.

Badreddine also makes a superb brik, that classic savory Tunisian pastry, his filled with butterflied sardines marinated in vinegar. Their slightly sweet-tart brininess pairs spectacularly with a bottle of the local zibibbo, which everyone around us seems to be drinking. Traditionally used in the production of fortified marsala, the grape has nowadays been repurposed to make fresh, light, low-alcohol quaffers like the one we're having: al Qasar by Rallo. Its label tells the story of Sicily's indebtedness to the Arab gardeners of yore who figured out how to grow bountiful fruit on the green hills all around us. It feels so rewarding to stumble upon a detail like this—a seemingly insignificant twiglet of information that manages to illuminate the entire forest of history and feeling we're trying to navigate.

It's not that it's been difficult to find proof of the Arab influence in Sicily. Quite the opposite, actually—in the short time I've been here, it's already clear that the island's Arab heritage is so pervasive that it's essentially woven into the fabric of life. It's simple: Hostaria San Pietro is as Italian as it is Maghrebi. Back home in Quebec, you don't need to look very hard to realize that the province is Frencher than the French. The province's motto is Je Me Souviens—it means "I remember"—although nobody knows exactly what it is they're supposed to be remembering. The same thing applies here: Mal d'Africa remains a phenomenon because the island's interconnected Arab-Sicilian past is still so alive today.

As I'm making my tipsy notes on a thin paper napkin, it occurs to me that Arabs first brought papermaking to this part of the world. The oldest dated European paper document was signed in 1102 in Sicily—and here I am almost a millennium later making my living by scribbling down thoughts like this: Would we even have paper napkins without Arab Sicilians? Is there anything we aren't unknowingly indebted to them for? Are we all Arab Sicilians without even realizing it?

This line of dreamy inquiry is pleasantly disrupted by the arrival of the pasta course—al dente busiate (a coiled fusili-esque pasta made in Trapani) tossed with garlicky almond and tomato pesto alla trapanese. It elicits cries of joy from everyone at our communal table. "Salute!" cries Scapagnini. He's having a blast. I'm ecstatically happy. It's the wee hours of a weeknight and we're sharing a beautiful, ridiculously cheap wine that carries a message of inclusivity and respect. Our mission, we agree over yet another toast, is a resounding success so far.

The next day we navigate through our zibibbo hangover from the town of Marsala (from marsa Allah, or "God's harbor"), where we see salt ponds dotted with brilliant pyramids of freshly harvested sea salt crystals, south along the coast. We stop in the town of Mazara del Vallo, whose central neighborhood—a warren of narrow, pretty streets—is called the La Casbah. We finish the day in Menfi at La Foresteria, a hotel run by Planeta winery. Here the chef prepares an edible illustration of Arab-Sicilian integration: pasta con le sarde. The dish, which combines minutes-fresh sardines with raisins, pine nuts, and saffron, is the archetype, the quintessence, of the way people ate here a thousand years ago—and the way they always will.

One thing about a dish as elemental as this: I'm starting to realize that it's impossible for a traveler like me to dissect things in any conclusive way. Sicily has had so many conquerors, and there's simply no way to pull apart all the intermingling strands of culture in order to ascertain what is precisely “Italian” and what's “Arab” and what's not anything of the kind. At a certain point—ideally sometime after having a homemade seafood couscous lunch in Ortigia and sampling the life-changing pistachio ice cream at Caffetteria Luca in Bronte—you have to give up trying to isolate the various influences and accept that countless aspects of life in Sicily have been informed by Arab culture in some way. It's deep and apparent and meaningful, but it's also a cloud of influence as dense and intangible as the lemon gelato sky that greeted me upon my arrival.

Perhaps what makes the Arab and Italian combination so compelling is simply the way it so naturally reflects the convoluted, mixed-up nature of life here today. Thoughts of caponata are running through my mind as we wind through the town of Ragusa, whose stone-cube buildings seem positively Libyan. This stunning mountainside community is also home to a bakery called Giummarra, which manufactures what may be the best street-food specialty I've had anywhere. It's called scaccia, and it's a baked pizza-bread roll-up filled with tomato sauce and D.O.P. caciocavallo cheese. Scapagnini is going on about how it's conceivably related to Tunisian briks, albeit oven-baked rather than deep-fried. The moment I bite into it, though, I lose interest in knowing where it came from or what its pedigree is. All I know is that it somehow encapsulates the magic I think of when I think of the timeless land of Sicily.

Get the recipe for Seafood Stew with Almonds and Couscous »
Get the recipe for Baked Rice Cake with Ham and Cheese »
Get the recipe for Caponata »
Get the recipe for Corkscrew Pasta with Eggplant and Tomato-Basil Pesto »
Get the recipe for Scaccia »

Palazzo Brunaccini
One of the best things about this modestly sumptuous palazzo is its location next to the souk-like Ballarò street market in Palermo.
Piazzetta Lucrezia Brunaccini, 9, Palermo

Baglio Sorìa Resort
This brand-new, super-stylish boutique hotel is found on the grounds of Firriato Winery's Baglio Sorìa property in the hills above Trapani.
Contrada Sorìa, Trapani

Locanda COS
The excellent COS winery operates this simple, elegant, 19th-century palazzo, whose courtyard reflects the tradition of Arab architecture.
S.P. 3, Vittoria

Hotel Gutkowski
Ortigia is an ancient island off the coast of Siracusa, and the excellent Hotel Gutkowski makes a perfect base from which to explore the surrounding area.
Lungomare di Levante Elio Vittorini, 26, Siracusa

Trattoria Piccolo Napoli
A classic trattoria that specializes in fresh seafood and also happens to make the best pastas and contorni in Palermo. Get anything with anchovies, pine nuts, and raisins.
Piazzetta Mulino a Vento, 4, Palermo

Hostaria San Pietro
The soul of Arab-Sicilian food today, Hostaria San Pietro is one of the best restaurants in Sicily. Drink zibibbo! Reservations are essential.
Largo Porta Galli, Trapani

Pasticceria Maria Grammatico
It's impossible to list all the masterpieces that Maria Grammatico crafts out of bitter almonds and Bronte pistachios—just savor each one.
Via Vittorio Emanuele, 14, Erice

Da Vittorio
The world's freshest tuna carpaccio is served at this beachfront restaurant in Menfi, where bluefin tuna are caught using an old Arab fishing technique.
Via Friuli Venezia Giulia, 9, Menfi

Viri Ku Cè
A meal at Scoglitti's seafood temple starts with tutto pesce: crudi of langoustines, plump white and red shrimp, crimson-tongued clams, and swordfish involtini—and that's just the appetizers.
Via Riviera Lanterna, 29, Scoglitti

A trip around Sicily is even more fun if Marco Scapagnini's tour company, NicheItaly, takes care of the logistics.