ish tostadas with Veracruzana salsa DSC5301

Fish tostadas, Veracruz style

I spent part of my junior year of college living in Spain. I was in the southern part of the country, in Granada, which is not too far from the Mediterranean Ocean. Because of this proximity, my host family ate a lot of seafood. And during Lent, it seems that’s all we ate.

We had fish stew, shellfish paella, tuna pizza, fish mashed potatoes, and fish croquettes. But one of my favorite dishes served was flaky white fish covered in a tomato sauce studded with green olives. All at once it was salty, acidic and sweet.

The Mexican state of Veracruz is on the Gulf of Mexico and is said to be where the Spanish first made their entry into Mexico. Because of this, much of the Veracruzana cuisine is still heavily influenced by Spanish cuisine.

Fish tostadas with Veracruzana salsa | Homesick Texan

The Spaniards introduced the herbs thyme, marjoram and bay laurel, which have become hallmarks of that state’s cooking. They also brought along olives and capers, so it’s no surprise that the signature salsa from that state uses all of these ingredients.

Salsa Veracruzana is a rich tomato-based sauce that isn’t too spicy. It’s cooked, so the ingredients meld together into one complex flavor instead of the several distinct flavors more often found in raw-blended salsa. Also, the bay leaves, thyme, and marjoram give it a distinctly different flavor than your usual tomato salsas made with just cilantro, jalapeno and lime salsas. That said there is also cilantro, jalapeno, and lime juice in this salsa, which makes it still taste distinctly Mexican.

And then there are the olives and capers that are found in this salsa. I love salty and acidic foods—they remind me of the sea. For this reason, I think that olives and capers also go very well with fish, thus making this salsa a perfect topping for a Mexican fish dish such as a tostada or a taco.

Fish tostadas with Veracruzana salsa | Homesick Texan
We have a few more Fridays in Lent, and I think if you aren’t eating beef or pork during this time, these fish tostadas are a hearty, meaty dish. I also enjoy it, however, because it takes me back almost 20 years to when I was a young student living in Spain.

5 from 1 vote

Fish tostadas with Veracruzana salsa

Servings 4
Author Lisa Fain


Ingredients for the salsa:

  • 1 tablespoon olive oil
  • 1 small onion, diced
  • 1 jalapeño, diced
  • 2 cloves garlic, minced
  • 1 (28-ounce) can crushed tomatoes
  • 12 large green olives, pitted, and diced
  • 2 tablespoons capers
  • 1/2 teaspoon dried marjoram
  • 1/2 teaspoon dried thyme
  • 1/4 teaspoon cayenne
  • 1 bay leaf
  • 1/4 cup chopped cilantro
  • 1 tablespoon freshly squeeze lime juice
  • Salt

Ingredients for the tostadas:

  • 4 corn tortillas
  • 1/2 cup oil, for frying
  • 4 (4-ounce) cod fillets
  • 2 teaspoons ground cumin
  • Salt
  • 1 lime, quartered
  • Chopped cilantro


  • To make the salsa, heat the olive oil in a pot on medium high, and then cook the onions and jalapeños for 10 minutes, stirring occasionally. Add the minced garlic and cook for another minute, then turn off the heat and then stir in the crushed tomatoes, scraping any brown bits that might have formed on the bottom of the pan. Mix well but don’t let it get hot.
  • Immediately place the tomato mixture into a blender, and puree into smooth. Pour the blended tomato mixture back into the pot, and add the olives, capers, marjoram, thyme, cayenne, bay leaf, cilantro, and lime juice. Bring to a boil and then simmer on low for 20 minutes. Taste and adjust seasonings and add salt. Remove bay leaf before serving.
  • Meanwhile, to make the tostadas, in a skillet, heat up the oil on medium high for 5 minutes. If you flick in a drop of water and it sizzles and pops, it’s ready. One at a time, add the corn tortillas and heat on each side for about a minute. Remove from oil, sprinkle with salt, and drain on a paper towel.
  • Season each side of the fish fillets with cumin and salt. Drain the oil from the skillet, leaving behind 1 tablespoon. Heat on medium, then add the fillets and cook on each side for about four minutes, or until the fish flakes. (You may have to do this in batches, depending on the size of you skillet).
  • Take cooked fish fillets, and place one fillet on a fried-corn tortilla, cover in salsa and garnish with lime and cilantro.

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *

Recipe Rating


  1. Justin Schwartz says:

    holy cow, I want to eat your blog

  2. unconfidentialcook says:

    These look so yummy, and that salsa sounds good enough to eat by the spoonful.

  3. Our local PBS station WNED Buffalo/Toronto airs the Made in Spain program with Jose Andres.

    If you haven’t seen it, it offers a very good look into the Spanish culinary scene and does a great job into tantalizing one to visit Spain in search of food and culinary adventure.

    Shout out to PBS for one excellent series.

  4. Made this over the weekend and the flavors were just right! I didn’t even need to puree the tomatoes, it was sort-of like a pasta sauce. I can imagine it also being great with fresh tomatoes, just slightly cooked.

  5. That’s nice to spend some time in Spain. This is a meal I would enjoy.