• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
  • Skip to footer
  • Paleo Recipes
    • Recipe Index
    • All Recipes
    • Instant Pot® Recipe Roundup
    • Paleo Packed Lunch Roundup
    • Whole30® Recipe Roundup
  • My Cookbooks
    • Nom Nom Paleo: Let’s Go!
    • Ready or Not!
    • Nom Nom Paleo: Food for Humans
  • Spice Blends
  • Shop
  • Events
  • Paleo Meal Plans
  • About
    • What’s Paleo?
    • About Michelle Tam
    • Nom Nom Paleo in the News

Nom Nom Paleo®

Paleo recipes and more from New York Times bestselling cookbook author Michelle Tam!

  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Pinterest
  • Twitter
Home » Blog » Recipes » Seafood » Fish in Veracruz Sauce

Fish in Veracruz Sauce

Jump to Recipe Jump to Video Print Recipe

Fish in Veracruz Sauce is a delicious 30-minute, one-pan dish featuring white fish fillets simmered in a zesty tomato sauce flavored with capers, olives, and onions. It’s so simple and delicious that you’ll rush to add it to your weekly dinner rotation!

An overhead shot of a skillet filled with white fish in Veracruz sauce.

I first tried Veracruz-style fish, pescado a la Veracruzana, at a restaurant in Cancun, and I was hooked (pardon the pun). And because dining out equals research and development for me, I came home ready to recreate a paleo, Whole30 and keto version of this classic Mexican seafood dish with easy-to-find pantry staples. It took me a while to perfect this dish, but my version of Fish in Veracruz Sauce can be on the table in less than 30 minutes!

What is Veracruz sauce?

Veracruz sauce is a tomato-based sauce from the region in the Gulf Coast of Mexico that features tomatoes, capers, olives, oregano and bay leaves. If you’re thinking that this sauce is reminiscent of a Mediterranean dish, you aren’t wrong—these are definitely classic Mediterranean ingredients! The Port of Veracruz is one of the oldest in Mexico and many regional Veracruz dishes—like this sauce—incorporate Mediterranean components that were originally brought over by Spaniards.

This sauce is super flavorful but it isn’t supposed to be spicy, so it’s perfect for folks who can’t handle the heat. And because I love shortcuts to deliciousness, my version utilizes canned fire roasted diced tomatoes to add a smoky depth to the sauce without adding extra prep time!

Adding a sprinkle of salt to Veracruz sauce in a skillet.

Feel free to change up the protein!

Although this dish is traditionally cooked with whole fish or fish fillets (e.g., red snapper, tilapia, cod, sea bass, etc.), you can definitely substitute a different protein. Some tasty swaps include shrimp, scallops, and boneless and skinless chicken breast or thighs. Simply season the protein with salt and pepper before simmering in the sauce until cooked through!

An overhead shot of white fish Veracruz in a skillet with sliced lime wedges on the side.

Ingredients

Raw ingredients to make fish in Veracruz sauce, a paleo, Whole30, and keto dish

  • Boneless, skinless white fish fillets: Although this dish is typically made with whole red snapper, I like to use boneless and skinless white fish fillets to make a fast and simple weeknight dish. Chilean sea bass, cod, tilapia, and halibut are great choices—just make sure they’re all the same thickness to ensure even cooking.
  • Fire-roasted diced canned tomatoes: I love the ease that comes with dumping in a whole can of fire-roasted diced canned tomatoes—no cutting, roasting or draining necessary!
  • Extra virgin olive oil
  • Yellow onion: The thinner you cut the onions, the faster they’ll soften in the skillet!
  • Anaheim pepper: I add diced Anaheim pepper for flavor rather than heat—this dish isn’t traditionally spicy so an Anaheim pepper, which is just a touch spicier than a bell pepper, is perfect.
  • Garlic cloves
  • Green olives: I love using pitted Castelvetrano olives because they’re nice and buttery.
  • Capers: Add a delightful tang and acidity that complements the fish.
  • Dried oregano
  • Dried bay leaf
  • Diamond Crystal kosher salt
  • Freshly ground black pepper
  • Fresh cilantro
  • Lime

How to make fish in Veracruz sauce

Heat a large skillet over medium heat. Once the pan is hot, add the oil.

Pouring olive oil in a large skillet in preparation of making Veracruz sauce.

Toss in the onion and sprinkle on some salt. Cook until softened, about 8 to 10 minutes.

Adding a small bowl of sliced onions to a pan filled with olive oil.

Stir in the peppers and garlic. Cook until fragrant, about 30 seconds.

A closeup of softened onions, minced jalapeño peppers, and minced garlic.

Add the canned tomatoes, green olives, capers, dried oregano and bay leaf.

A hand is adding a dried bay leaf to a skillet with canned diced tomatoes, sliced green olives, capers, and dried oregano to make homemade Veracruz sauce

Bring the sauce to a boil and decrease the heat to maintain a simmer.

An overhead shot of a skillet filled with simmering Veracruz sauce.

Taste the sauce and season with salt and pepper if needed.

A hand is adding freshly cracked pepper to a skillet filled with homemade Veracruz sauce

Pat the fish filets dry with a paper towel and sprinkle both sides with salt and pepper.

Patting raw fish filets with a paper towel before seasoning them with salt and pepper.

Nestle the fish filets into the sauce and place some of the sauce on top of each filet.

A pair of tongs is tucking raw fish fillets into a skillet filled with Veracruz sauce.

Cover the skillet and cook on low heat for about 10 minutes or until fish is opaque and cooked through, about 140°F on an instant-read thermometer.

A closeup of cooked fish filets in homemade Veracruz sauce

Sprinkle on some fresh cilantro…

A hand is sprinkling minced fresh cilantro on a pan filled with white fish in Veracruz sauce

…and serve the fish with lime wedges so you can squeeze on some fresh lime juice before taking a bite.

A closeup of white fish filets in Veracruz sauce with lime wedges on the side.

To keep this paleo, Whole30, and keto, you can serve this dish with cauliflower rice in lieu of white rice. It also tastes great served with my Instant Pot Crispy Potatoes!

Other Paleo Seafood Dishes

  • Hash Brown Fish (page 150 in Nom Nom Paleo: Let’s Go!)
  • Ginger Scallion Fish Fillets (page 156 in Nom Nom Paleo: Let’s Go!)
  • Umami Fried Shrimp (page 164 in Nom Nom Paleo: Let’s Go!)
  • Lobster Tails with Thai Red Curry Sauce (page 170 in Nom Nom Paleo: Let’s Go!)
  • Air Fryer Fish Sticks
  • Fried Calamari
  • Shrimp and Avocado Salad
  • Paleo Walnut Shrimp

Looking for more recipe ideas? Head on over to my Recipe Index. You’ll also find exclusive recipes on my iPhone and iPad app, and in my cookbooks, Nom Nom Paleo: Food for Humans (Andrews McMeel Publishing 2013), Ready or Not! (Andrews McMeel Publishing 2017), and Nom Nom Paleo: Let’s Go! (Andrews McMeel Publishing 2022).


PRINTER-FRIENDLY RECIPE CARD

An overhead shot of white fish Veracruz in a skillet with sliced lime wedges on the side.
Print Recipe
4.90 from 19 votes

Fish in Veracruz Sauce (Paleo, Keto, Whole30, Gluten Free)

Fish in Veracruz Sauce is a delicious 30-minute, one-pan dish featuring white fish fillets simmered in a zesty tomato sauce flavored with capers, olives, and onions. It’s so simple and delicious that you’ll rush to add it to your weekly dinner rotation!
Prep Time10 mins
Cook Time20 mins
Course: Dinner
Cuisine: Mexican
Keyword: fish, gluten-free, keto, low carb, nom nom paleo, nomnompaleo, paleo, Whole30
Servings: 4
Calories: 405kcal
Author: Michelle Tam

Ingredients

  • 2 tablespoons extra virgin olive oil
  • 1 medium yellow onion halved and thinly sliced
  • Diamond Crystal kosher salt 
  • 1 Anaheim pepper seeded and finely diced
  • 3 garlic cloves minced
  • 14.5 ounce canned fire roasted diced tomatoes
  • ½ cup green olives pitted and cut in half
  • 1 tablespoon drained capers
  • ½ teaspoon dried oregano
  • 1 dried bay leaf
  • freshly ground black pepper
  • 4 white fish filets (skinless and boneless) about 6 ounces each and 1-inch thick (sea bass, red snapper, halibut, cod, or tilapia)
  • ¼ cup minced fresh cilantro
  • 1 lime cut into wedges

Instructions 

  • Heat a large skillet over medium heat and add the oil when the pan is hot.
  • Toss in the onion and sprinkle on some salt and cook until softened, about 8 to 10 minutes.
  • Stir in the chopped pepper and garlic. Cook until fragrant, about 30 seconds.
  • Add the tomatoes, green olives, capers, dried oregano, and bay leaf.
  • Bring the sauce to a boil and decrease the heat to maintain a simmer. Taste the sauce and season with salt and pepper if needed.
  • Pat the fish filets dry with a paper towel and sprinkle both sides with salt and pepper.
  • Nestle the fish filets into the sauce and place some of the sauce on top of each one. Cover the skillet and cook on low heat for about 10 minutes or until fish is opaque and cooked through, about 140°F on an instant-read thermometer.
  • Sprinkle on some fresh cilantro and serve the fish with lime wedges so you can squeeze on some fresh lime juice on before taking a bite.

Video

Notes

What can you serve with Fish in Veracruz Sauce?
To keep this paleo, Whole30, and keto, you can serve this dish with cauliflower rice in lieu of white rice. It also tastes great served with my Instant Pot Crispy Potatoes!
Tried this recipe?Mention @nomnompaleo or tag #nomnompaleo!

Nutrition

Calories: 405kcal | Carbohydrates: 12g | Protein: 21g | Fat: 31g | Cholesterol: 7mg | Fiber: 3g | Sugar: 4g
41

Thrive Market   LunchBots   Real Plans

Reader Interactions

Comments

  1. Sanja says

    March 30, 2022 at 2:04 am

    Is there a substitute for anaheim peppers that you would recommend?

    Reply
    • Michelle Tam says

      March 31, 2022 at 10:41 pm

      You can use a jalapeno pepper but it will be spicier! If you don’t want it too spicy, add 1/2 a bell pepper.

      Reply
      • Inna S says

        February 28, 2023 at 11:14 pm

        5 stars
        Such a great recipe! I made it several times already and my family loves it. The sauce is amazing. Thanks for another keeper of a recipe

        Reply
  2. Brenda says

    March 30, 2022 at 4:53 pm

    Could you use haddock?

    Reply
    • Michelle Tam says

      March 31, 2022 at 10:38 pm

      Yes!

      Reply
  3. Lilia says

    March 31, 2022 at 12:14 am

    5 stars
    This recipe was so tasty and delicious. Everyone my family really enjoyed it. This will absolutely be made again. Thanks.

    Reply
  4. Jerilynn says

    April 2, 2022 at 3:04 pm

    5 stars
    This was absolutely delicious. I gave the recipe to my husband to create and now he thinks he’s finally becoming a good cook! This is definitely a good option for having company over. Thanks Michelle!

    Reply
  5. Deb Merle says

    April 2, 2022 at 7:57 pm

    5 stars
    This is delicious!! If it seems not quit done in 10 minutes – don’t keep cooking it – trust the recipe!
    Thanks Michelle!

    Reply
  6. AL says

    April 25, 2022 at 1:26 pm

    5 stars
    Super tasty and easy! I left off the pepper for my spice sensitive kiddo but will try a bell pepper next time.

    Reply
  7. Beth says

    June 14, 2022 at 1:42 am

    I would love to make this recipe when we are in Maui! What Hawaiian fish do you recommend?

    Reply
    • Regina Chan says

      June 14, 2022 at 3:03 pm

      Any white fish will do!

      Reply
  8. Sristi says

    July 14, 2022 at 9:02 pm

    This dish looks perfect and knowing all your other recipes I have tried i am 100% sure it will turn out amazing. Can this sauce be made ahead and frozen in portion for meal preps?

    Reply
    • Regina Chan says

      July 18, 2022 at 6:18 am

      I haven’t tried but I don’t see why not!

      Reply
  9. Texas Judy says

    July 29, 2022 at 10:45 pm

    5 stars
    Make this often! For color I add red orange green and yellow peppers chopped small. For company taste I add a fourth cup of Sherry and mix.
    It looks beautiful on the table not to mention it tastes wonderful.

    Reply
  10. Jane says

    August 22, 2022 at 1:29 am

    We loved this recipe. Have made this before with regular diced tomatoes but the fire-roasted upped the flavor. Forgot to add the pepper until late in the game but it still came out really good. Definitely will make again soon.

    Reply
  11. Sharon says

    March 5, 2023 at 1:46 am

    5 stars
    Really good and easy.

    Reply

Leave a Reply Cancel reply

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

Recipe Rating




Logged in as . Edit your profile. Log out? Required fields are marked *

Primary Sidebar

Archives

About Nom Nom Paleo Nom Nom Paleo Cookbooks Nom Nom Paleo App Nom Nom Paleo Spices
  • Email
  • Facebook
  • Instagram
  • LinkedIn
  • Pinterest
  • RSS
  • Twitter
  • YouTube

Popular Posts

  • A slice of paleo and dairy free asparagus quiche on a plate in front of pie pan with quiche inside. Asparagus Quiche (Paleo, Whole30, Gluten Free, Dairy Free)
  • An overhead shot of the world's best braised green cabbage, carrot coins, and sliced onions in an oval casserole pan. Two hands are holding the handles with towels. World’s Best Braised Green Cabbage
  • An overhead shot of a platter topped with Instant Pot (Pressure Cooker) Crispy Potatoes Instant Pot (Pressure Cooker) Crispy Potatoes
  • An overhead shot of a tabletop with bowls of Pork and Napa Cabbage Soup Pork and Napa Cabbage Soup (Whole30, Instant Pot)

Footer

COPYRIGHT© NOM NOM PALEO LLC. All rights reserved. The content on this website may not be copied or reproduced in any manner whatsoever without prior written permission.

HOME  •  PRIVACY POLICY  •  CONTACT

Copyright © 2023