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

5 from 1 vote (1 rating without comment)

Leave a Reply

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

Recipe Rating


  1. Made these tonight with halibut and they were absolutely delicious. I’ve been wanting to make pescado Veracruzano for a while; thanks for the wonderful recipe!

  2. ¿Can huachinango veracruzana be far behind? ¿Or filete tampiqueña?

    And in this same tradition, we used to order something called tacos portuguesas at restaurants in the border area of S Texas in the 1950s. A sauced corn tortilla fold-over (envuelto?) that I have not been able to replicate. ¿Have you ever heard of these?


  3. I’m a regular reader of a blogger from Spain and she lives in the same area you were in and she cooks great seafood dishes all the time.

  4. Lisa Fain says:

    Justin Schwartz–Thanks–that’s high praise!

    UnConfidentialCook–Oh, and trust me, I did eat the sauce by the spoonful.

    Tommy–I’ll have to keep an eye out for that show, sounds wonderful!

    Meghan–Yay! Glad you loved it, and I agree, it is a bit like a pasta sauce.

    Helene–I love Spain!

    Susan–Awesome! I’m so glad you enjoyed it!

    TBSamsel–I haven’t but let me investigate and see what I find.

    Cynthia–Now that makes sense!

  5. Wow! My wife pointed out your blog to me today since I decided that I needed a creative outlet aside from cooking. I have to tell you that your blog is great and I subscribed. I, too, am from the west (AZ) and really miss decent Mexican food. What they call Mexican here in DC really is horrible and I find myself avoiding going to them if my friends dont want to go to one of the few “APPROVED” places. Im going to try the fish tostadas soon.