Main dish Seafood

Fish tostadas, Veracruz style

ish tostadas with Veracruzana salsa DSC5301

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.

ish tostadas with Veracruzana salsa DSC5301
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


  1. 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.

  2. 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.

  3. 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.

  4. 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).

  5. Take cooked fish fillets, and place one fillet on a fried-corn tortilla, cover in salsa and garnish with lime and cilantro.

  1. These sound absolutely delicious. I love fish tostadas and the Salsa Veracruzana is so unique. I can’t wait to give this one a try. Thanks!

  2. Yum! Love the capers and olives, sounds delicious.

  3. Culinary Wannabe

    I’m stuck on the “fish mashed potatoes.” Seriously?!

  4. lisaiscooking

    Just delicious. I want this for dinner every day. Can’t wait to make the salsa.

  5. I want to know more about the fish mashed potatoes too! Were they made with salt cod? I bet that would be delicious. I *heart* veracruzana sauce too. Its like puttanesca to the nth degree.

  6. I am definitely going to make this in the next few days. I have some red snapper, will probably use these instead.
    I’ve been wanting to try Salsa Veracruzana for a while, might as well make it myself! Thanks for the recipe!!

  7. Yay! Thanks for the lesson! Looking forward to making these. I heart your blog!

  8. noble pig

    This is a beautiful dish. One of my favorite visits to Spain was when I spent time in Granada…such memories and yes all the fish!

  9. This sounds fantastic. But I too want to hear about the fish mashed potatoes. Go figure!

  10. Innkeeper Seely

    I will try anything with capers or anchovy but can’t warm up to olives. I’ll try this with an extra dash of capers and skip the olives.

    Dish on the fish mashed potatoes. Sounds like something I should make since I live in a fishing village

  11. Anonymous

    That sounds absolutely delicious!

  12. Ooh 9 times out of 10 why do I come to your blog when I am already hungry? Now my stomach is growling again.
    I love fish and am not eating enough of it. Mmmm and yes capers do go well with fish – I remember eating grilled rainbow trout at home with slits cut under the skin, stuffed with capers and garlic.

  13. I haven’t had fish tacos before, but I wnat them now! They sound so good.

  14. masdevallia

    It’s always such a pleasure to read your posts. The photos are beautiful and the personal history is a treat to read. I used to work in a place that specialized in Baja style fish tacos. I’m happy to expand this out to 1) a tostada 2) Vera Cruz! My husband is going to be very happy that I read this post!!

  15. Lisa Fain

    Phoo-D–It’s very delicious. Enjoy!

    Maggie–Capers and olives are wonderful with the fish!

    Culinary Wannabe–You’re not the only one, sounds like I need to put it on the blog.

    LisaisCooking–It’s good for breakfast, too!

    Ann–Nope, canned tuna.

    JBeach–Red snapper will be a wonderful substitution.

    Sara–You’re welcome!

    Noble Pig–I love that city and I hope I can spend a long chunk of time there again someday.

    Kathi–You’re not alone–I need to write something about it!

    Innkeeper Seely–That would be fine as they’re still briny and salty.

    Olivia–I’ve warned you before about stopping by on an empty stomach! And I love the sound of that grilled trout with olives stuffed under the skin. Mmmm!

    Masdevallia–Thank you so much! I’m very pleased that you enjoy stopping by!

  16. Justin Schwartz

    holy cow, I want to eat your blog

  17. unconfidentialcook

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

  18. 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.

  19. 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.

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

  21. 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!

  22. tbsamsel

    ¿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?


  23. 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.

  24. Lisa Fain

    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!

  25. 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.

Leave a Reply

Your email address will not be published.

Recipe Rating