The sandwich didn’t look like much, and neither did the restaurant. Called a prego, it seemed little more than a few slices of beef tucked between halves of an English muffin-like roll. Lisbon’s everyman lunch served in a minimalist working class café—white tiled walls, chalkboard menu, wood-block tables.

Appearances deceive. Incredibly moist, the sandwich at Tasquinha Ilha da Madeira combined juicy slabs of beef, garlicky butter and bright yellow mustard. The combination was rich, filling and meaty. But the clincher was the roll itself. Called a bolo do caco, it was crispy-chewy and had a barely detectable sweetness that balanced the other ingredients. It was this sweetness that particularly drew us to these rolls.

Made fresh daily at the back of the café, the rolls turned out to have a connection to the restaurant’s name. Bolo do caco come from the Portuguese island of Madeira, where they are served with most meals. Traditionally baked on a basalt slab (the caco) set over a wood fire, they originated with the North African slaves brought to work on the island’s sugarcane plantations.

The slaves often made griddled flatbreads similar to Moroccan harcha or Algerian kesra, but the bolo do caco were sweeter and moister than those breads, and both tender and crispy. One ingredient made the difference—mashed sweet potato. Sweet potatoes thrived on Madeira, and it’s said that the islanders mixed them into the yeasted dough to stretch their more limited supply of wheat.

But the mashed sweet potato didn’t just stretch the dough, it also moistened it. The high fiber content holds onto moisture, yielding the roll’s signature lighter, more tender crumb as well as adding color.

These days, of course, the rolls typically are grilled in a skillet rather than on a stone. Bakers boil and mash sweet potatoes, combining them with warm water, yeast and all-purpose flour before kneading. Some let the dough ferment for days, others let it rise for just an hour before dividing it into rolls for a second rise.

At Milk Street, we loved the subtle sweetness and tender crumb the sweet potato added, but we wanted to highlight it a bit. To reinforce the flavor, we added a tablespoon of honey to the potato cooking water and used that starchy water to make the dough. We also opted to start the rolls in a skillet but finish them all at once on a baking sheet in the oven so the entire batch could be served at once.

The rolls came out warm and crispy, fluffy and cakey with a fine crumb. They were perfect for a hearty sandwich, but just as delicious eaten on their own, split in two and slathered with a simple garlic-chive butter.