Are you trying to eat more seafood? Here’s a roundup of easy, tasty, and healthy Nom Nom Paleo Whole30 Seafood Recipes!

A collage of 8 Nom Nom Paleo recipes that are Whole30 compatible seafood recipes. The red banner at the bottom says paleo, gluten-free, and low carb

Many Nomsters in my Facebook Group have commented that they’re cooking more seafood at home, but they need more instruction on how to cook fish and shellfish properly. Are you in the same boat? I’ve compiled some of my most useful seafood cooking tips and favorite Whole30 fish and shellfish recipes below!

Seafood Buying Tips

  • Buying high quality seafood can be confusing so I always refer to the Seafood Watch Program guide to steer me in the right direction.
  • Buy your seafood from a trusted fish market and pick it up on the day you serve it to ensure freshness. I even ask the fishmonger to pack my seafood with ice so it stays cold until I can get it in my fridge. If you don’t have access to fresh seafood locally, a great place online to buy high quality frozen seafood is Vital Choice.
  • Stock up on frozen shrimp for weeknight dinner emergencies because you can quickly thaw them in about 5 to 10 minutes. Simply throw the frozen shrimp into a colander and run lukewarm water on them until the shrimp thaw, tossing them every so often. Then, blot the thawed shrimp dry with paper towels and continue with the recipe!
  • Stock up on individually quick frozen fish fillets! Throw the fillets in the fridge the night before or in the morning so they’ll thaw by dinnertime. If the fish is vacuum sealed, open the packaging before thawing to prevent potential bacterial overgrowth. Read this article to learn why you should open vacuum packaged fish before thawing.
  • Canned fish is a great and inexpensive way to get more seafood into your diet! For many years, I’ve kept a can or pouch of tuna in my backpack or purse so I always have a protein-rich, ready-to-eat snack or light meal at my disposal. You never know when you’ll be stranded with no food options and unlike nuts or dark chocolate—I only crack open the can when I’m truly hangry.

How Do You Know if Seafood is Cooked Properly?

Use a meat thermometer to check if your fish is cooked properly! My reliable and accurate Thermapen Mk4 is the key to perfectly cooked seafood. Although the FDA recommends that fish be cooked to at least 145°F, I like to use these recommended temperatures for seafood.

Can I cook seafood in an air fryer?

The short answer is: yes! An air fryer is simply a countertop convection oven that circulates hot air. If you want convert one of my oven seafood recipes for the air fryer, a good rule of thumb is to  decrease the temperature by 25°F and decrease the cooking time by about 20 to 30%. Also, as I’ve recommended above, always use a good meat thermometer to check for doneness!

Here are 8 Whole30 Seafood Recipes

Whole30 Spicy Tuna Cakes

These portable and delicious spicy tuna cakes are sure to win over your family! Make extra, because leftovers can be stored in the fridge in an air-tight container for up to 4 days or frozen for up to 3 months.

Two paleo and Whole30 spicy tuna cakes are on a white plate.

Spicy Tuna Cakes by Michelle Tam https://nomnompaleo.com

Spicy Tuna Cakes

4.88 from 75 votes
These portable spicy tuna cakes filled with sweet potato and jalapeño peppers are delicious, tender and Whole30-friendly!
View Recipe

Whole30 Paleo Shrimp Tacos

If you’re sick of ground beef tacos, here’s a quick and healthy weeknight supper that’s a cinch to throw together!

An overhead shot of Paleo Shrimp Tacos on a bed of lettuce. There is a bowl of Avocado Crema on the top left.

Paleo Shrimp Tacos by Michelle Tam / Nom Nom Paleo https://nomnompaleo.com

Paleo Shrimp Tacos

4.91 from 22 votes
These Paleo Shrimp Tacos are a simple and delicious weeknight supper! Plus, you can make this keto and Whole30 recipe in a flash!
View Recipe

Whole30 Poached Cod in Tomato Sauce

This 5-ingredient recipe takes less than 30 minutes to make and will satisfy even your pickiest eater!

An aluminum pan with poached cod in tomato sauce topped with parsley.

An overhead shot of Poached Cod in Tomato Sauce.

Poached Cod in Tomato Sauce

4.83 from 29 votes
This Whole30- and keto-friendly Poached Cod in Tomato Sauce is so simple and delicious! You can get it on the table in just a few minutes on a busy weeknight!
View Recipe

Whole30 California Hand Roll

Missing sushi on a Whole30? This keto-friendly and rice-free California Hand Roll is packed with crab and avocado and it’s so easy, even the kids can help you make homemade sushi!

Three gluten-free and Whole30 California hand rolls stacked on a black plate, next to a dipping bowl with coconut aminos.

A closeup of a California hand roll on a gray plate next to a small bowl filled with coconut aminos.

California Hand Roll (Whole30 Crab and Avocado Temaki)

4.92 from 12 votes
These Whole30-friendly California Hand Rolls filled with crab and avocado will scratch your sushi itch!
View Recipe

Whole30 Tandoori Fish

Tandoori fish has quickly become my go-to Whole30-friendly seafood recipe on busy weeknights because these tender and aromatic fillets are insanely easy to throw together, and they pack a big punch of flavor.

A closeup of perfectly cooked Tandoori Fish on a plate with sliced lemons.

Tandoori Fish by Michelle Tam / Nom Nom Paleo https://nomnompaleo.com

Tandoori Fish

4.84 from 12 votes
Tandoori fish has quickly become my new go-to fish recipe on busy weeknights! These tender and aromatic fillets are so simple to throw together and pack a big punch of flavor that your whole family will enjoy. This healthy recipe's versatile, keto, Whole30-friendly, and delicious!
View Recipe

Whole30 Crab Cakes

These crab cakes, which I affectionately nicknamed “Paleo Krabby Patties,” are crispy on the outside and packed with tender crab on the inside! Because there’s no breadcrumb filler, the crab shines through. Trust me: no one will miss the gluten!

A plate filled with paleo crab cakes, red cabbage slaw, and lemon wedges.

Two plates filled with paleo crab cakes, red cabbage slaw, and lemon wedges.

Paleo Crab Cakes (Whole30, Keto)

4.79 from 19 votes
These crab cakes, which I affectionately nicknamed “Paleo Krabby Patties,” are crispy on the outside and packed with tender crab on the inside! Because there’s no breadcrumb filler, the crab shines through. Trust me: no one will miss the gluten!
View Recipe

Whole30 Tonnato Sauce

Tonnato is a creamy and tangy sauce made with anchovies, capers, and canned tuna that tastes waaaaay better than it sounds. It’s a Whole30- and keto-friendly sauce that tastes delicious drizzled on veggies and roasted meat!

An overhead shot of a white plate filled with colorful raw vegetables and a small white ramekin filled with tonnato sauce.

Tonnato Sauce by Michelle Tam / Nom Nom Paleo https://nomnompaleo.com

Tonnato Sauce

4.91 from 10 votes
Tonnato is a creamy, tangy sauce made with anchovies, capers, and canned tuna. It's so simple to make and tastes delicious drizzled on veggies and roasted meat! Don't doubt it, try it!
View Recipe

Whole30 Easy Teriyaki Salmon

Wondering what else to make with my All-Purpose Stir-Fry Sauce? If you thought sweet-and-savory teriyaki was off the menu because you’ve cut out gluten and refined sugar, think again: this ridiculously easy teriyaki salmon recipe is flavorful, Whole30-friendly, and perfect for weeknights!

A platter of Easy Teriyaki Salmon, a simple Whole30, paleo, gluten-free weeknight dinner!

A platter of Easy Teriyaki Salmon, a simple Whole30, paleo, gluten-free weeknight dinner!

Easy Teriyaki Salmon

4.91 from 21 votes
This ridiculously easy teriyaki salmon recipe is tasty, Whole30-friendly, and perfect for weeknights! Just marinate in All-Purpose Stir-Fry Sauce, bake, garnish, and eat!
View Recipe

Want more Whole30 Seafood recipes?

Check out the rest of my Whole30 seafood recipes here!

Other Whole30 Tips

Completing a Whole30 doesn’t have to be hard. That’s why I’ll be posting Whole30-friendly recipes to my Facebook page all month long to keep you inspired! I’ll also be popping in frequently to my personal Nomster’s Facebook group to answer any questions. Don’t forget about my cookbooks that have paleo and Whole30-friendly meals as well as my iOS app!


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


 

About Michelle Tam

Hello! My name is Michelle Tam, and I love to eat. I think about food all the time. It borders on obsession. I’ve always loved the sights and smells of the kitchen. My mother was (and is) an excellent cook, and as a kid, I was her little shadow as she prepared supper each night. From her, I gained a deep, abiding love for magically transforming pantry items into mouth-watering family meals.

Other Recipes You May Like

Leave a comment

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

1 Comment

  1. I tried your method for smoked salmon in given receipe. Turned out amazing!!! After an hour and a half spritzed it with a mixture 1/3 cup apple juice and 3 tablespoons of Worcestershire sauce. Thanks sooo much for sharing your expertise!!!!