Whole30® compliant recipes from Paleo Newbie

Grilled Salmon Taco Wraps with Avocado Sauce

Get ready to grab a handful of healthy goodness with this easy paleo recipe for light and luscious salmon lettuce wrap tacos.

These are yummy, nutritious, Whole30 compliant, and so very simple to make.whole30 compliant recipe mark

Grill some salmon, pop the pieces into a buttery green cup, add a layer of fresh cole slaw mix, and finally top it all with this sensational Avocado Sauce. That’s all there is to it!

For the grilled fish seasoning, I used my Everyday Seasoning Salt. It adds another layer of savoriness to the grilled salmon – but just about any seasoning you have handy that complements fish will do the trick.

For my “soft shell” tacos, I chose butter (bibb) lettuce. A great alternative would be Romaine leaves or even plain old iceberg lettuce would work too.

For the fixings in this paleo fish wrap, I simply went with a fresh coleslaw mix. Shredded cabbage or shredded carrots are good alternatives if a pre-packaged slaw mix isn’t your thing. Just a little lime juice, fresh cilantro, oil and dash of salt is about all you need to jazz up the crunchy slaw mix. Toss in a sliced Anaheim or jalapeño pepper if you want to turn up the heat a little.

And to really speed up the prep on this one, just make the Everyday Seasoning Salt and the Avocado Sauce ahead of time (the sauce will keep fresh in your fridge for a few days.)

If grilling season has already passed you by, no worries.

You can oven bake your seasoned and oiled salmon fillets. Just place them skin-side down in a greased baking dish and cook at 400ºF for around 14-18 minutes.

Or, you can easily pan fry your fillets. First put them skin-side up in a frying pan with a little oil over medium-high heat for a few minutes until lightly seared, then flip the fillets over and cook skin-side down until the flesh feels slightly firm to the touch.

This recipe makes such an easy, healthy and light meal. Not a lot of carbs, plenty of protein, healthy omega-3, and an awesome avocado sauce that really takes these paleo salmon lettuce wraps to the next level.

That’s it friends. Just a simple paleo lunch or light dinner entrée you can whip up in no time. There’s plenty of room in this recipe to get creative and add your own personal touches, so have some fun with it.

Enjoy! Leave a comment and let me know what you think!

salmon taco wraps with avocado sauce easy paleo recipe

Grilled Salmon & Butter Lettuce Taco Wraps with Avocado Sauce Recipe

September 12, 2017

  • Yields: 4-6 salmon lettuce wrap tacos
salmon taco wraps with avocado sauce easy paleo recipe


1-2 tbsp Everyday Seasoning Salt recipe link here (or substitute with your favorite grilled fish seasoning)

1/4 cup Avocado Sauce recipe link here

2 fresh salmon fish fillets

1 head of butter lettuce (aka Boston or bibb lettuce)

2-3 cup cole slaw mix or shredded cabbage

1/4 cup fresh cilantro leaves, chopped

1 lime, juiced

Salt, to taste


1Ideally, prepare the Everyday Seasoning Salt and Avocado Sauce before starting (See recipe links in ingredients list above)

2Season salmon filets generously with Everyday Seasoning Salt (or your favorite seasoning). Lightly pat to adhere, and drizzle with some olive oil or avocado oil

3Heat grill to medium high. Grill salmon 5-8 minutes, turning once. Cook just until fillets easily flake but are still moist. Remove from grill and set aside temporarily to cool. (Instead of grilling, salmon fillets can be pan-fried or baked if desired)

4In a small mixing bowl, combine cole slaw mix (or shredded cabbage) with chopped cilantro leaves and juice of 1 lime. Salt to taste

5Rinse butter lettuce leaves, and spin-dry in salad spinner, or lightly blot dry with paper towels. Select the best cup-shaped leaves to create your lettuce wrap tacos

6Break apart cooled salmon fillets. Place salmon pieces inside lettuce wrap tacos, and sprinkle each with cole slaw mixture

7Finish each lettuce wrap taco with a healthy drizzle of Avocado Sauce


Trina’s Everyday Seasoning Salt

Hey, what’s shaking in your kitchen?

Here’s what’s been going down in mine – lots and lots of this super-easy Everyday Seasoning Salt!

When your quick meals could use a dash of something to give them a bigger and bolder flavor, this simple spice mix will definitely get your taste buds dancing.

I came up with this all-purpose spice mix for my meal prep guide and cookbook, but what the heck. I wanted to share it with you now because I know you’ll be reaching for it again and again.

This one’s simple yet powerful. An herb & spice blend that only needs 8 common ingredients – you probably have all of them sitting in your spice rack right now. And of course this easy seasoning recipe is paleo, gluten-free and Whole30-compliant.

simple paleo and gluten free seasoning mix

Instantly boost the flavor of any dish with this quick and easy spice blend. The Everyday Seasoning Salt recipe is paleo and gluten-free. Makes a little over 1/2 cup so it should last you a good while!

It’s just what you need to jazz up almost any dish. Eggs, chicken, fish, potatoes, roasted veggies – you name it. That’s why I named it Everyday Seasoning Salt – you’ll find yourself using this one just about every day to perk up any dish on the fly.

Take note, this seasoning salt is a little sassy with a touch of heat. The overall effect is more savory than spicy I think – but if you’d prefer a milder version, just scale back on the recipe’s chili flakes, or leave them out altogether.

I’m pretty generous when spreading the love around with this one – especially when I’m using it to add an extra spark of flavor to my grilled dishes. Just adjust how much you use to suit your own personal taste.

Shake up a batch of this easy seasoning mix (it makes 1/2 cup or so) and store it sealed in your cupboard away from heat and light.

But keep it within easy reach … for the next couple of easy paleo recipes I post here on Paleo Newbie, you’ll need it.

Shake things up in your kitchen today and try this easy Everyday Seasoning Salt recipe for your next quick meal!

Paleo and gluten free Everyday Seasoning blend

Trina’s Everyday Seasoning Salt Recipe

August 23, 2017

  • Yields: Makes about a 1/2 cup
Paleo and gluten free Everyday Seasoning blend


2 tbsp Salt

2 tbsp Garlic Powder

2 tbsp Onion Powder

2 tbsp Paprika

1 tbsp Chili Powder

1 tbsp Parsley

1 tbsp Pepper

1 tsp Red Pepper Flakes (optional, or adjust to taste)


1Add all the spices to a container or plastic bag and shake well to combine.

2Store sealed in away from heat and light.


Paleo Mini Taco Nacho Party Peppers

Impress your guests with this awesome party appetizer! Colorful, delicious, easy and Whole30 compliant. Instant party on a platter for your summer shindigs!

Savory Paleo Chicken Chowder

There’s nothing like a hot and steamy bowl of easy homemade chicken chowder on a cold and rainy day. Read more

Paleo Slow-Cooked Italian Pot Roast

There’s nothing that warms your home and your heart quite like the aroma from this classic American dish – a savory pot roast simmered until it’s fall-apart tender and delicious. Read more