Tasty grilled fish taco recipe Mexican-style [+ special sauce secrets]

by Joost Nusselder | Last Updated:  January 10, 2023

Always the latest smoking tips & tricks?

Subscribe to THE ESSENTIAL newsletter for aspiring pitmasters

We'll only use your email address for our newsletter and respect your privacy

I love creating free content full of tips for my readers, you. I don't accept paid sponsorships, my opinion is my own, but if you find my recommendations helpful and you end up buying something you like through one of my links, I could earn a commission at no extra cost to you. Learn more

I recently purchased a Stainless Steel Char-Broil Gas Grill, as I wanted to test my food smoking skills after being a fan and enthusiast for more than 2 years now. I really enjoyed the outcome of my grilling escapade making fish tacos!

The secret to the tastiest grilled fish tacos is to use flakey white fish like cod, mahi-mahi, halibut, or even tilapia when grilling. This recipe uses cod. The rest is just fresh cabbage and my own special sauce.

Today we’ll use it to make the tastiest grilled fish tacos that will surely impress any seafood lover!

Char-Broil 463377319 Performance 4-Burner Cart Style Liquid Propane Gas Grill, Stainless Steel

(view more images)

Grilling fish tacos on a gas grill

The Char-Broil gas grill is one of my favorite grills well under $500, but you can make this recipe for fish tacos on any gas grill.

Fish also tastes great when grilled on charcoal, so no worries if you are working with a charcoal grill.

Previously I tried doing the grilled calamari steak and simple cat fish fillets, this time I’ve experimented with delicious codfish, and a tasty mayo sauce in tacos.

How to buy a bbq smoker video
How to buy a bbq smoker video

I came up with an amazing recipe that’s truly mouth-watering and very satisfying!

To be honest I was actually scared at first to let my friends try my fish tacos because they might not like how it tastes.

So I decided to sample it alone and make improvements in case it didn’t meet my expectations.

I think I like these fish tacos even more than the pulled pork recipe I showed you guys last week!

brinkmann grill

You may also want to read my review of the best portable gas grills that you can take anywhere

You can use any white fish for this recipe but I prefer cod because it doesn’t break and flake apart while you’re grilling it.

Read on for the recipe, and some great tips on making the best fish taco sauce.

Grilled cod fish tacos recipe

Grilled Cod Fish Tacos

Joost Nusselder
Delicious seasoned grilled cod stuffed into tortillas with shredded cabbage and a mayo taco sauce. This recipe is sure to delight seafood lovers looking to try a Mexican-style grilled fish dish.
No ratings yet
Prep Time 15 minutes
Cook Time 15 minutes
Course Main Course
Servings 8 tacos
Calories 249 kcal

Ingredients
  

  • 1 lbs cod fillets wild-caught
  • 8 corn tortillas
  • 1.5 cups green cabbage
  • 1.5 cups red cabbage
  • 2 tbsp fajita seasoning
  • 3 tbsp lime juice freshly squeezed
  • 2 tbsp olive oil
  • 1 green or spring onion
  • 1/2 cup cilantro fresh
  • 1/2 tsp salt

For sauce

  • 1/2 cup mayonnaise
  • 1/2 cup Greek yogurt
  • 1.5 tbsp lime juice
  • 1 tbsp hot sauce
  • 1/4 tsp garlic powder
  • 1/4 tsp salt kosher

Instructions
 

  • Preheat the grill on medium-heat (375 – 450 degrees F).
  • Wash the fish and pat it dry with a paper towel.
  • Spread a bit olive oil on the fish to make the seasoning stick.
  • Sprinkle fajita seasoning on both sides of each fillet.
  • Place fish on cooking grates but not directly over flames. Cook for approximately 4 minutes. Flip it and cook for about another 2-4 minutes depending on how browned it is.
  • Once the fish reaches an internal temperature of 130 F, remove it and break the fillets apart with forks. Set aside.
  • Slice all the cabbage into thin slices or grate it for the slaw.
  • In a bowl, mix the sliced cabbage, lime juice, and spring onion. You can add a 1/2 tsp of salt for flavoring.
  • Char or warm the tortillas on the grill for a few seconds.
  • Now add the fish and slaw into each tortilla and top with the sauce and fresh chopped cilantro.

Notes

  • You can use 1-2 lbs of fish, depending on the size of your tortillas. If they’re the larger kind of tortilla you’ll need more fish and more cabbage. Adjust seasonings accordingly.
  • If you can’t find cod, use any fresh white fish fillets for a similar mild fishy flavor. 
  • Add more kosher salt to the fish if your fajita seasoning doesn’t have salt. 
 

Nutrition

Calories: 249kcalCarbohydrates: 15gProtein: 14gFat: 15gSaturated Fat: 2gPolyunsaturated Fat: 7gMonounsaturated Fat: 5gTrans Fat: 1gCholesterol: 31mgSodium: 405mgPotassium: 389mgFiber: 2gSugar: 2gVitamin A: 321IUVitamin C: 19mgCalcium: 61mgIron: 1mg
Keyword Fish
Tried this recipe?Let us know how it was!

Fish taco recipe substitutions & variations

As with any recipe, you can make changes to suit your own tastes and options better.

Fish

You can make a delicious fish taco with any white fish.

I prefer cod, halibut, and mahi-mahi (that one is more expensive) but it’s meatier. However, many people use cheaper tilapia fillets or fresh sea bass.

It doesn’t matter – these fish options are all tasty when grilled for tacos.

Technically, you can use grilled salmon too, but it’s denser and chewier but if you like fattier fish instead of white fish, you can use it.

Wondering how a gas grill compares to a pellet grill? I’ve compared the two grill types here

Fillings and toppings

Cabbage (both purple cabbage and green taste great) is the basis for the taco slaw.

Grilled fish tacos need a bit of crunch that only cabbage can give. Add some shredded carrots or iceberg lettuce for extra crunch.

Fresh lime juice is a must-have ingredient for any authentic fish taco recipe. You can add the lime juice to the slaw or drizzle some on the grilled fish for a tangy flavor.

Then, add the lime juice to your sauce too!

You can also experiment with seasoning spices and herbs. Top the fish tacos with some chili powder, chili flakes, paprika, or smoked sea salt.

There’s no real limit to the spices you can use.

Tortilla

The classic corn tortilla is probably the best for fish tacos but you can use other alternatives if you don’t like them.

Wheat flour or plantain tortillas work too!

Just be sure the tortillas are large enough that you can easily assemble the tacos.

What is the best fish for tacos?

Lean and flaky white fish, such as halibut, mahi-mahi, cod, tilapia, or sea bass, is the perfect choice for making delicious BBQ grilled fish tacos.

Whitefish is better because of its texture and flavor, which works well with the bold flavors of the BBQ sauce and Mexican spices used in this tasty dish.

The white fish is flaky and falls apart in the tacos so it’s easy to eat and melts in your mouth.

Whitefish cooks really fast on the grill (about 5-6 minutes total) and thus is easy to make.

What is a good sauce for fish tacos? Three recipe options

I think the classic fish sauce award goes to the famous tartar sauce.

But there are other options too! Just be sure to add some lime juice – it’s the one tangy ingredient that can make or break a fish sauce.

If you prefer store-bought sauces, here’s what to try:

  • Tartar sauce
  • BBQ sauce
  • Sriracha mayo
  • Sour cream

Option 1: Mayo chipotle sauce

There are many different sauces that can be used on fish tacos, but the most popular option is a mayo-based sauce.

A bold, creamy sauce that is tangy, spicy, and savory is the perfect pairing for your fish tacos.

Here’s how to make mayo sauce for the fish tacos:

First, grab a bowl to mix all your ingredients.

Then combine the following:

  • 1/2 cup of mayo
  • 1/2 cup of Greek yogurt or plain yogurt
  • 3 tbsp of chipotle sauce
  • lime juice (about 3 limes)
  • 1/2 tsp garlic powder
  • 1 tsp salt (you can use less if you want)

You can also add some smoked chili to the mix to spice things up even more!

Some people prefer to use sour cream instead of Greek or plain yogurt for a thicker sauce, it’s up to you.

Option 2: Cilantro lime sauce

Grab a bowl and mix the following:

  • 1/2 cup of Greek yogurt
  • 1/3 cup of mayonnaise
  • the juice of 1 lime
  • 1/4 tsp of salt
  • 1/4 tsp of ground black pepper
  • 1/4 tsp of garlic powder
  • 1/4 tsp of dried dill

Chop up 1/3 cup of cilantro and add into your sauce then mix well.

Option 3: Herbs & sour cream sauce

This one is similar to tartar sauce but it’s a better upgrade.

Grab a bowl and then combine the following:

  • 1/2 cup of sour cream (reduced fat is best)
  • 1/2 cup of mayonnaise
  • the juice of one lime
  • 1/2 tbsp of dried dill
  • 1/2 tbsp of dried oregano
  • 1/2 tbsp of cumin
  • 1/4 tsp chili powder
  • 1 tbsp of minced capers

You can really add any herbs and spices you like to this sauce.

Takeaway

Now that you have the recipe for the Mexican-style fish tacos with mayo sauce and the cooking method for it, all you need to do now is get your grill fired up.

You will enjoy it as much as I did, I promise.

Worried your grill cover might actually cause your grill to rust? I explain how to make sure your grill stays in good condition while undercover here

Joost Nusselder, the founder of Lakeside Smokers is a content marketer, dad and loves trying out new food with BBQ Smoking (& Japanese food!) at the heart of his passion, and together with his team he's been creating in-depth blog articles since 2016 to help loyal readers with recipes and cooking tips.