Khalid Aziz's father opened the restaurant 33 years ago, when the family first arrived from Mozambique, a country that, until its independence in 1975, had been occupied by Portugal for over four centuries. His father's patrons were almost exclusively other Mozambican emigrants. Aziz, who shares his father's name, took over three years ago after working in London as an interpreter. One of the first changes the junior Aziz made was to remove bitoque from the menu, a classic Portuguese steak-and-eggs dish that his father had served as a gesture to the native friends his Mozambican customers would occasionally bring in.

Aziz wasn't sure if the young, smartphone-wielding, born-and-bred Portuguese clientele began to come in before or after he and his wife, Jeny, scrubbed the remaining local dishes from the menu. But they came and packed the place—and the accolades followed.

"Something's changed in the last few years," he told me as I took a bite of a chamuça, a crispy fried sachet of coarsely ground beef seasoned with curry and fresh herbs.

"Young people like the food, so they bring their parents—they want to take them to a place that's trendy. The parents come in and say 'I took you here when you were a kid.' 'No, no!' say the kids. 'It's new!'"

As a general rule, Portugal has launched its people into the world rather than taken wanderers in; in the 18th and 19th centuries, the only immigration to speak of came from Spain and Galicia. But when the dictatorship dissolved in 1974, a first wave of migrants arrived from its former colonies in Africa and India; and when Portugal joined the EU in 1986, Brazilians, Chinese, Indians, and Eastern Europeans joined the ranks of new job-seeking residents. And in the last few years, as the country has made its way back from the 2008 economic crisis, an exuberant, creative food scene has flourished in Lisbon. Though many restaurants still proudly serve a predictable, familiar Portuguese menu—cod-and-potato-based dishes, hearty paella-esque rices, and meat-and-bean stews like feijoada—native chefs are starting to open up to outside influence, and foreign-born ones are seizing on local produce and seafood, featuring them in recipes from home.

"People here tend to evaluate food based on memories of what their grandmothers gave them to eat," said the chef, ex-artist, and onetime punk rocker, Hugo Brito. At Boi Cavalo, the restaurant he opened nearly three years ago in a tiny former butcher shop on one of the vertiginously hilly, skinny streets of Alfama, Brito aims to challenge diners' expectations with surprising takes on those traditional ingredients and grandmotherly dishes.

On my first visit to Boi Cavalo, I ate smoked horse mackerel placed atop a stiff puddle of alvarinho wine gelée; and baby razor clams, a Portuguese classic, served on crispy gyoza filled with acorda, a savory traditional bread pudding. Every dish was, without fail, rigorously interesting, every plate a combination of the expected and deliciously strange.

Brito likes to take beloved Portuguese ingredients—mackerel, lupine beans, and graham crackers, a favorite childhood snack—and give them twists from countries thousands of miles from home. "The question I always ask," he said, "is am I adding something to it or not?"

He often finds inspiration deep in Lisbon's immigrant-heavy neighborhoods—Mouraria, literally the Moorish quarter, and Alfama now abound with residents from across Africa and Asia. He encountered palm oil in Angolan, Bissau-Guinean, and Mozambican restaurants, and it proved to be the perfect, missing ingredient in a dish of pomegranate-marinated hake, buttery graham cracker croutons, and pumpkin purée. And he decided to dress a cockle dish with slices of unripe green mango after learning at Jesus é Goês, a hill away from Boi Cavalo, that tart green mango juice often accompanies oysters in Goa.

Jesus Lee Fernandes—an Indian born in Goa to a Catholic mother and a martial arts-loving father—opened the slip of a restaurant three years ago. At the end of the tiny space, where brightly painted Hindu icons leap across the walls, an altar to Bruce Lee presides over Goan food gone highlighter-bright with Portuguese ingredients: fresh pink shrimp folded into a biryani, stews dotted with green okra. I devoured a plate of golden chickpea fritters served alongside a wildly flavorful paste of finely ground cilantro, coconut, green chile, and tamarind. When there were no more fritters left, I scooped the paste straight from the bowl with my hands. As I licked my fingers, Fernandes described a tasting menu he was cooking up that included fresh clam samosas and oyster curry: Portuguese ingredients, Goan-ized.

In a country that's long been deeply traditional in the kitchen, even the subtlest tweak to an old standby is exciting, a sign of a shift in the way cooks are cooking, and diners responding. At Leopold, an intimate, experimental restaurant in Mouraria, chewy soy-pickled kombu seaweed intensified the tenderness of a slab of seared beef from the Azores; at Taberna da Rua das Flores, I tried a feijoada de lulas that swapped out the pork and beans in the usually black stew for squid, simmered in a hearty red chorizo broth until butter-soft. And one Wednesday afternoon, at Rosa da Rua, a small restaurant in the hip Bairro Alto neighborhood, Brito took me to eat a riff on cozido à portuguesa from Africa's Cape Verde islands.

The quintessential Portuguese stew is often made with beef shin, pork sausages, blood sausage, and a fermented, smoked kind known as farinheira. But to the customary cozido medley, the chef, Maria Pina, added stewed pear and quince. She supplemented the usual white beans with meaty chickpeas and stewed cabbage. She snuck in pumpkin, cauliflower, and sweet potato—hearty elements found in a traditional Cape Verdean stew, cachupa. The combination of pungent flavors, rich textures, and bright colors was surprising. It captivated Brito. The pumpkin, that quince, the restaurant replete with a wine-glass-tinkling lunch crowd—all exciting indications, to those who were paying attention, of the new potential of the Portuguese plate.