Home > Recipes > Dietary > Paleo > Paleo Paella (Whole30, low-carb)

Paleo Paella (Whole30, low-carb)

July 9, 2019

(updated March 14, 2023)

4.47 from 13 votes
Pin Recipe
Jump to Recipe

What’s Inside: I took an authentic Valencia-style paella recipe and made it paleo with cauliflower rice and some gut-boosting bone broth! You’ll love this easy, flavorful seafood paella dish that you can customize and really make your own.

Paleo Paella with Cauliflower Rice via Food by Mars (Whole30, low-carb)

Paella is a favorite dish of mine, especially in the summer with seasonal ripe tomatoes and bell peppers ready to go.

I was so lucky to be able to travel to Majorca, Spain a few years ago with my little sister, where we joined a cooking class and learned how to make authentic mixed seafood paella while we sipped cava (Spanish sparkling wine), ate soppressata and got to learn from a talented chef all the ins and outs of authentic Spanish cooking (this is also where I learned how to make a tortilla). I made some minor substitutions to make it grain-free with my beloved cauliflower rice and tossed in some bone broth because, well, why wouldn’t I?! I’ve also made this with white rice which is, of course, delicious, it does take longer as the rice needs to cook for much longer and you would need more liquid to get the rice cooked to the way you want it, so the cauli rice is actually quicker (and makes it a low carb paella if that’s your thing)!

Tips for delicious Paella:

  1. You MUST use Saffron or no deal. Find this in an international aisle or on Amazon. Go with a RED SPANISH SAFFRON. Yes, it can be a little pricey, but it will last you a long time and it goes A LONG WAY in Spanish cooking!
  2. Try to be patient as you develop the layers and flavors, allowing time for the liquid to cook and absorb will be worth it. (Paella isn’t soup!)
  3. Add saffron with or after liquid so the taste really develops (and so it doesn’t burn).
  4. The proteins can be interchangeable, there are Paellas without seafood, and no meat out there – you can really make it your own with anything on hand or leftovers (that’s the true nature and history of the dish).
  5. Fresh tomatoes > canned tomatoes if you can and if they’re in season! (which for summer, they most definitely are!)
  6. I like using a round cast iron for the job, but any large pan will do.
  7. If you want a more mild (less spicy) tasting paella, half the amount of chorizo used and half the red peppers. Then taste and season/add more if you’d like.
Paleo Paella with Cauliflower Rice via Food by Mars (Whole30, low-carb)

Recently, in my private meal plan and coaching community, we had a Paleo Paella cooking class and everyone loved it! This is a fun dish to prepare in a group and eat straight out of your pan, family-style.

paella cooking class photos

Provecho!

More Recipes to Try:

Paleo Paella with Cauliflower Rice via Food by Mars (Whole30, low-carb)

Paleo Paella

4.47 from 13 votes
Perfectly spiced mixed seafood paella recipe that's paleo and low-carb made with cauliflower rice for the win! You will love this classic Spanish dish.
Print Pin
Author: Alison Marras
Prep Time: 15 mins
Cook Time: 45 mins
Yield: 4

Ingredients

  • 1 head cauliflower riced (or 3-4 cups cauliflower rice)
  • 6 oz. wild shrimp peeled & deveined
  • ½ lb. mussels cleaned, pre-steamed & open on one shell
  • 1 Tbsp extra virgin olive oil
  • ½ lb. ground chorizo (or chorizo inside casing, sliced – use a compliant brand for Paleo/Whole30 free of sugar and nitrates)
  • 1 small yellow onion chopped
  • 1 large or 2 small fresh tomatoes grated
  • 1 garlic clove minced
  • 1 red bell pepper chopped
  • Pinch sea salt
  • Pinch black pepper
  • 1-3 Pinches saffron (to taste)
  • 1 Pinch sweet paprika (to taste)
  • 3-4 Tbsp Picada (see below)
  • 1 cup bone broth I use Bonafide Provisions Chicken or you may use any broth you'd like

Picada

  • 1 bunch fresh cilantro
  • 1/2 yellow onion, chopped
  • 1 green bell pepper
  • 1/4 cup extra virgin olive oil
  • 2 tsp white wine vinegar

Instructions:

  • Make the picada by mixing ingredients in a food processor.
  • Pre-steam mussels by cleaning the shells (they should be closed), and trimming off any "beards". Add them to a pot or saucepan with 1-inch boiling water and cover to steam on medium. After 3-4 minutes, check and you're done when they're (mostly) all opened. Discard any closed mussels. Drain, and set opened mussels aside, optionally discarding the empty side of the shell for presentation.
  • Add oil to paella pan (skillet) over medium heat, add chorizo and break up with spoon as you cook. Once cooked, remove from pan and set aside.
  • To the same paella pan, add onions and tomato to cook for approx. 6-7 mins.
  • Next, add the picada, red pepper, and garlic to cook for 3 more mins while stirring.
  • Add cauliflower rice and stir to coat, then add back the chorizo, taste test to adjust seasonings as needed. If it needs paprika at this point, add it in (the chorizo may add enough).
  • Flatten the cauli rice mixture and POUR the bone broth over top, add in a pinch or two of the saffron and lightly stir in to distribute. Taste again to season as you like. Let it cook for 15 minutes and check in – cook until moisture is well absorbed.
  • Add shrimp and mussels on top, optionally garnish with more cilantro and continue to cook on medium-low for 10 more minutes. You can cover for a few minutes towards the end so the shrimp gets golden. Serve (optionally with lemon wedges).

Notes:

Taste and season to your liking along the way!
This is the paella pan I use, any large skillet will do.
Diet: Spanish
Keywords: paella, paleo
Course: Main Course
-Alison Marras
This post may contain affiliate links. Please read my disclosure policy.

browse more recipes:

Cauliflower Entrées Fish & Seafood Low-carb Paleo Recipes Summer Whole30
Start nourishing your body easily + consistently

I believe your healing journey with real food can be a stress-free lifestyle, filled with joy and flavor, giving you the time and energy to live more.

Subscribe to my newsletter, and you’ll receive the latest recipes and my best wellness tips to make this a lifestyle!

Join Now

join the conversation

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

Recipe Rating




This site uses Akismet to reduce spam. Learn how your comment data is processed.

17 comments

  1. This was a wonderful recipe. We all enjoyed this flavorful version of paella. I will be making this again. Thank you so much Alison !!

    Reply

  2. This was an amazing recipe. I will definitely make it again. It was flavorful and everyone enjoyed it. Thank you Ali !!

    Reply

  3. My first taste of paella and it was wonderful! I went with shrimp and bay scallops, which I paired with homemade chorizo because of my paprika allergy. This recipe makes extra picada which is okay since it is a delightfully fresh sauce that I can use with other dishes. But . . . if you double the paella recipe like I did, you might only want to make a single batch of the picada. I wished I had a photo to share because the panful of paella with seafood nestled on top was beautiful. FYI, you can use a wok for this recipe if you don’t have an official paella pan.

    Reply

    • You rocked it, Cheryl!! Thanks for sharing your tips on the homemade chorizo to get around that paprika sensitivity – yumm!

      Reply

  4. This was amazing. My husband is from Spain and he makes paella all the time. The flavors on this one were spot on. Much easier to prepare and much lighter. Especially for those of us with anti-inmune conditions, that we try to stay away from rice, this is perfect. We didn’t even miss the rice, to tell you the truth. Even our 15 y.o. daughter gobbled it up. We will make it again, definitely. You have a home run, Alison. Thank you so much. I love being part of your Nourishing You membership. You are transforming my health and my life. Un abrazo hermosa!

    Reply

    • You guys are the best!! I’m so happy you’re with us and joined the cooking class, your paella turned out beautifully and I’m honored you all enjoyed it. xo

      Reply

    • Thanks for asking, Darlene! I just clarified when to add it during saute steps in the directions. Enjoy!

      Reply

you might also like