Pilaf, pilav, plov, pulao, paella. The khichdi of softened fragrant rice tumbled with meats, seafood and vegetables, permutated to suit individual tastes or larger cultures, radiates far and wide from its Persian beginnings. Paella was high on my mind when on my first trip to Spain. I had eaten it a few times, but never been satisfied. I was measuring it against a vacant reference point, of course, but my instinct told me each time that I was merely flirting with potential. I knew there was something greater I was missing. Hype usually starts from truth.

So, when I arrived in Madrid, I followed the signs. They all touted the terribly tantalisingtoothsomeness of their own version of the dish. I believed them all — the blindness of an excited tourist. I popped into a nondescript-looking eatery in a downtown spot and was reminded of a common misconception: just because a joint is well worn (read: rundown) doesn’t make it authentic. What appeared before me was a congealed mess of soggy rice and shrivelled sea critters — it was glutinous, flavourless and deeply dissatisfying. Thank heavens for Pedro, then.

Andres, my buddy in New York, had told me to get in touch with his friend Pedro when I got to Madrid. Pedro looked shattered when I narrated my experience and took it upon himself to right this horrible transgression exacted on me by ruthless tourist trappers. He was going to make me a paella. Pedro’s boyfriend Frank looked at me as if I’d struck jackpot. He didn’t do this often.

The word paella is said to have actually been derived from paelle, the Old French word for pan. The dish was evidently born in Valencia, a town the Moors had taught to grow rice. The most typical version of that region, Paella Valenciana, is composed of rice, chicken, rabbit, duck, snails (the latter two are optional), beans and green vegetables. Other versions include Paella de Marisco, wherein seafood takes the place of the meats and the beans; and Paella Mixta, a combo of meats, seafood, vegetables and sometimes beans.

Pedro was passionate, precise and assiduous. The seafood was off-the-boat fresh. He shucked the mussels, drained the squid of its ink and left the shrimp heads on. He made a stock of monkfish bones, and shared his secret: when the stock is nearly done, toss in a couple of prawns and blend them down with the softer fish bones. He prepared the sauce— with olive oil, garlic, onion, peppers and tomato — drizzled in the stock and added the thick-grained arborio rice. The seafood was added at the home stretch and served as soon as the rice had cooked. Like risotto, paella must be eaten right away. Watching Pedro glide through the process, textures shape-shifting as aromas suffused the air, I was champing at the bit. We dug in. Forkfuls interspersed with mouthfuls of a Riojan red. I finally understood what the fuss was about.

Madrid done, I hopped the superfast AVE train to Seville with a quick stopover in Córdoba. Spain’s fourth-largest city, Sevilla (Seh-vee-ya), as it’s known to its peeps, makes claims of the best nightlife, most stylish people (saith the Lonely Planet) and the best tapas bars in Andalusia.

The word tapa is drawn from the Spanish verb tapar, which means ‘to cover’. Many versions of how the appetiser was born exist, but most sound apocryphal. The most plausible one goes like this: time ago bartenders would cover the drinks they served with either a piece of bread or a card to keep out fruit flies that thirsted for the often-sweet libations, such as sherry. This practice expanded to the placing of a snack upon the cover. The salty tidbit would create thirst, encouraging patrons to drink more. We’re not talking wafers and peanuts here, though. Tapas come in a mélange of forms, flavours, styles and consistencies.

In most Spanish-style bars, you’re bound to find patatasbravas. The authenticity of the recipe is rarely guaranteed, but a tasty version is nearly always assured — how wrong can you go with chunks of fried potato slathered in a garlic aioli or spicy tomato sauce? Other typicals include albóndigas (beef meatballs in a gently spiced onion and garlic-based sauce); aceitunas (stuffed or virginal green or black olives); gambas al ajillo (tiny prawns sautéed simply in olive oil with garlic); chorizo, cho-ree-so or the lisped cho-ree-tho, but never cho-ree-tso, ( little rings of spicy cured pork sausage); espinacas con garbanzos (spinach and chickpeas sautéed in olive oil with garlic, shallots and cumin); tortilla de patatas (Spain’s renowned potato omelet, probably the most commonly sighted tapa in the country); and, of course, croquetas (bullet-shaped dumplings made of flour, oil, milk, eggs, breadcrumbs and ham).

Jamón, or Spanish ham, is a national obsession. It is found within dishes, outside of them, in sandwiches or simply layered on a plate, awaiting a suitor to consummate a luscious and lascivious act. Spaniards fixate so much over it that someone named a movie after it: JamónJamón was the delicious Penelope Cruz’s debut. The nation eats so much of it you can barely turn a corner in Madrid without bumping into one of the many specialty ham restaurants called Museo del Jamons scattered about. Visitors to these eatery-cum-charcuterie are greeted by giant legs of ham dangling from the rafters.

What the Spaniards call tapas, the Basque call pintxos (pronounced peen-chos). They might string me up for that, though. The proud folk of Euskadi, as the inhabitants of a chunk of northern Spain refer to the land they would like to run as a separate country, take those bar bites to far higher levels. The best way to experience Basque culinary excellence without having to shell out a month’s pay at a Michelin-starred restaurant in San Sebastian (it has seven) would be to simply hit the city’s old quarter and trawl its agglomeration of tavernas.

At each one I was greeted with a tantalising display of their specialty. The variety was hard to keep up with. Carne (meat), mariscos (seafood), verduras (vegetables) — cut, cooked, stacked, twisted and spread wildly, madly, erotically, speared to slices of bread by the toothpicks that give the finger foods their name (pintxo translates to spike or thorn). Haute versions included little pots of aged-cheese risottos and seared slabs of foiegras. This was no ‘version’ of tapas; it was a whole other bar code.

My gusto for gluttony took me further, to the coastal town of Getaria for grilled fish, brined white asparagus and txakoli (pronounced as cha-ko-lee), the region’s famed white wine. Happy, but hungering for highfalutin, I made my way west to Bilbao. I was told if you can’t afford Martín Berasategui’s thrice-Michelined restaurant (the tasting menu is €195 before booze, tax and tip), you can still savour his genius at the restaurant in the Guggenheim. Every mouthful was a shock of flavour, balance, texture and sensation. And, this was merely the commoner version.

As satisfied as I was with my culinary explorations through other parts of Spain, Barcelona was where I had my most transformative gastronomical moment. Just off La Ramblas, the central pedestrian strip that’s thick with musicians, mimes, prestidigitators and pickpockets, sits La Boqueria. The sprawling market is not just a hub where tourists, locals and chefs procure the city’s freshest produce. It also houses a number of counters purveying local culinary delights.

My friend and fellow food fanatic Yet Fan had flown down from Amsterdam to join me in some serious devouring. We waited impatiently for a couple of stools to free up at a busy food counter called El Quim. Like hungry hyenas, we launched into the food the moment we found seats. Barely able to translate the large menu, we randomly picked, pointed and nodded. And, we inhaled. Every delectation that appeared before us was welcomed, savoured and demolished. Then came manna: chipirones con huevosfritos. Those words, they sound like a romantic serenata by Jose Feliciano. To my palate, they were divination on a dish.

This is how simply it’s done: heat olive oil, toss in chillies and garlic; add baby squid; sauté rigorously. In a separate pan, dribble in an inch of olive oil; break in two eggs; swim them in and about the oil until done, the yolks still intact. Slide eggs onto plate, heap squid all over. Shovel copiously into mouth, slippery chipirones melding in gleeful copulation with gooey eggs. Chew gently, masticate joyously. Let mind wander, conjuring up ways of proposing to the national assembly of Spain to bestow chipirones con huevosfritos the honour of being Spain’s national dish.