Tuesday, April 20, 2010

Paleo Paella

Paella (pie-Ay-ya) is an old Spanish dish that my fiance and I were lucky enough to try while in Barcelona. This picture is from our trip when we tried some squid ink paella.

From Barcelona

I've never actually made regular paella let alone paleo paella, but it seemed like it could be done. It was either going to turn out to be a complete failure or a success, and I'm happy to tell you that it wasn't an epic paleo-fail. This recipe takes a little under an hour, so it's not fast, but it can be done on a weeknight.

Here is what you need:

From Paella

Starting at the mussels at the bottom: 1 lb of mussels (4.99), 1 orange ancient pepper(0.25), 1 red ancient pepper(0.25), 4 cloves of garlic (0.08), one can of diced tomatoes (1.59), cauliflower (2.34), parsley (0.05), 1 yellow onion (1.00), 1 lemon (0.25), paprika, 2-3 lbs of chicken thighs (3.24), 8 large shrimp (4.99), and (not pictured) a hot sausage (2.16)- we used a hot Italian sausage (salamini) our deli guy recommended. That's a total of 21.19, or roughly 4-5 dollars per serving. This is one of the pricier meals I've made, but it is worth it, I promise.

I prepped all the veggies and meat before starting to cook. It makes life a lot easier and I don't feel as rushed as I cook. You'll need to grate the cauliflower, grate the garlic as well as chop the onions, pepper, and sausage. This is also a good time to clean off the mussels. Just put them in a strainer and run your fingers over the shells, removing anything you can. If any of the mussels are open and don't close if you tap them on the counter, throw them away. They're dead.

From Paella
Use the larger holes on your grater.

From Paella

From Paella
Cut the sausage into half circles.

Once all the chopping and cleaning is done, start by frying the chicken thighs in some olive oil. Make sure the oil is nice and hot so that you get a good sear on the chicken.

From Paella

From Paella

When the chicken has a good sear on each side (about 6 minutes on the first side and only about 4 on the second), set the chicken aside. Use the oil and chicken fat to fry up the onions, sausage, and peppers.

From Paella

When the veggies are golden brown add the garlic. Make sure to keep stirring when the garlic is in the pan. You don't want the garlic to sit around a have a chance to burn. Garlic gets really bitter when it burns.

From Paella

Stir for about 2 minutes, then you'll add the chicken back in along with the tomatoes and a handful of paprika.

From Paella

Stir in the paprika and bring that up to a boil. Once it starts to bubble, add a lid and put bring heat down to about half. As that simmers, start heating up some olive oil in another pan. When that is hot, add the grated cauliflower. It will take a while for the cauliflower to turn brown which is fine because the paella needs to simmer for a while. Keep stirring and just don't let the cauliflower burn. Eventually it will turn brown.

From Paella

When it is brown, add 100 ml of chicken stock and wait for it to evaporate. When it does, your cauliflower is done. Just set it aside.

From Paella

It should take about 20 minutes for the cauliflower to be ready, so it's the perfect timing to get back to the paella. It can't really simmer too long with the lid on, so don't get stressed if it's taking your cauliflower longer to cook or if you have to do it in batches.

From Paella

Now is the time to add the mussels. This is the perfect time to double check for dead guys. They'll be the ones that are open and won't close when you tap them on the counter. Throw them away.

From Paella

From Paella

Add the mussels to the mix and put the lid back on. The mussels will open up in about 2 minutes. At this point, add the shrimp and wait another 2 minutes.

From Paella

Remove the lid and that's it! You've just made paella. Don't you feel classy? Not yet? Ok, add some parsley and lemon then, Mr. Belivedere. Now you're first class all the way.

From Paella


Kristy A. said...

Wow! That looks delicious! I love your photos and description. Nice job! I will have to try your preparation of cauliflower rice. I bet that browning adds some great flavor for fried rice. I will add this to my paleo repertoire! Thanks!

Paleotron said...

@Kristy Thanks for the comment. You could probably brown the cauliflower a little more than I did in the pictures, but I was getting pressed for time and had to rush things a little. I hate calling it rice because it doesn't have quite the same texture, but it serves the same purpose. To me, rice is just a vessel for sauce and other flavors and the cauliflower "rice" fills that role nicely. Real paella has some delicious crusty rice bits on the bottom of the pan and I'm working on a way to replicate that without burning down my apartment building. If you try the recipe, please let me know how it goes.

Adam said...

Another post, another great recipe! Please keep up the good work with this blog. Your recipes, articles, and insight into the paleo lifestyle are invaluable to me as well as the other readers of this site. Thank you.

Paleotron said...

@Adam Thanks, for commenting. I really appreciate the compliments. I'm just learning and figuring out my own paleo path just like everyone else. I'm just happy others can learn from the journey.

Shawn said...


I live in Barcelona and so was excited when I saw "Paleo Paella" ... but, where is the "rice" in the final photo...

Also, a couple of general comments about paella:

- Paella is traditionally made a la "risotto" by repeatedly boiling down the ingredients with a homemade seafood stock. The stock is normally made with bodies/bones of fish and shrimp/shellfish and simmered for several hours, preferably overnight.

Note: all shellfish should be served "whole" (i.e. with bodies & shells, unpeeled) with the paella

- The best part of paella is cracking the whole prawns and sucking out the "guts" in the head... makes prawn tails seem like throwaway meat in comparison

- Paella traditionally gets its yellow color from adding saffron...

- Chicken is not a traditional ingredient for the "mar i muntanya" (surf & turf) style paella, but rather rabbit... though I guess in the U.S. chicken is a suitable substitute based on the general lack of availability of rabbit..

- The best paellas are accompanied by "all i oli" a traditional catalan mayonnaise made from nothing but olive oil and garlic (egg is used in many restaurants but is not the real deal. (Here's a recipe, translated with google:

Still, looks super good- and Paleo!


Paleotron said...


You are definitely right that this is not a traditional paella. Having eaten a few in your home city of Barcelona, I will be the first to attest to that. I completely understand some of your concerns about the dish.

-The cauliflower rice is under the chicken. I didn't notice it was hidden - good eye.

-I try to keep the recipes as simple and streamlined as I can without compromising on flavor too much. Making the stock from scratch would definitely add flavor, but would also take some time that a lot of people would not have the patience to do.

-I live in Chicago. One of the drawbacks of being in the midwestern US is that my grocer only has prawns at certain times and I often have to fight off old ladies from the neighborhood to get to them. Shell on shrimp was as good as I could do this week. Trust me, I was just as disappointed as you are about missing out on prawns because the "guts" are one of the tastier parts of the dish.

-I debated on getting saffron for a few minutes while in the spice aisle, but decided that the $15 for the subtle (albeit delicious) flavor wasn't worth it. A theme on my blog is trying to keep costs in check as going paleo can be quite expensive.

-You're right on the rabbit - It's available here, but isn't always easy to come by.

-I'm excited to try the all i oli. Thanks for letting me know about it. I love learning about new food.

I appreciate your expertise on the subject. If you have any ideas for other Spanish dishes that could be done in a paleo way, don't hesitate to make a request! Have a good one, Shawn.

Shawn said...


Thanks for the response... I'm actually American, but have been here in Barcelona for 3 years now.

One of my favorite dishes, that you'll never find in a restaurant, is a Catalan Peasants' Meat Rice. A poor man's paella if you will and affectionately known by my friends (whom I have won many with this dish..) as "Shawn's Beef-rice"

I rented a room with an elderly couple and learned invaluable amounts of insights from them, not the least of which this recipe- Which is a century old (or more) family recipe from a village in the Pyrenees.

It's traditionally made with normal rice, but would be interesting to try it with cauliflower rice!


Arros de la Maria amb All i Oli !

IMPORTANT- The quality of ingredients is crucial in this dish...

First make a Sofrito (Sofregit in Catalan, literally "Slow fry" in English)

This is basically a confiture of onion, tomato and olive oil.

Chop 2 large yellow onions
Meanwhile in a frying pat begin heating on low a copious amount of the best olive oil you can afford (anywhere from a few tablespoons to several large dollops, depending on personal tastes)
Now "slow fry" the onions on as low of a heat as you can stand.

*Note, a sofregit can be made in anywhere from 20 minutes to 4 hours. I normally go for 1 or 1 1/2 hours, but I've had satisfactory results in 30 minutes... adjust the heat on the stove accordingly.

The onions should not blacken nor burn in anyway, but rather sweat and, I don't know to put this gastronomically, blob up.

When the onions are well cooked add an equivalent amount of tomato (fresh, skinned and deseeded or canned paste).

Add 2-3 cloves chopped garlic
Liberally add sea salt, paprika, thyme, rosemary, black pepper...etc

When you can no longer distinguish the onions from the tomatos, the sofregit is ready!


Make your rice (cauliflower in this case)a good amount, in real rice measures a few cups a person...
Fry 1 lb ground beef (the best you can afford), Drain
Make your all i oli (see recipe i above comment)

Combine the sofregit and ground beef, mix well

Plate the rice, forming "volcano craters" on top

Fill with the beef mixture

Top generously with the fresh all i oli

Mix it up and eat!

It takes a while but is totally worth it and I guarantee you'll want more!

Plus it's cheap!

*Serves 2-4 depending on appetite

Hope you get a chance to try it, Dave!


Paleotron said...

That sounds really good, Shawn. I'll do my best to try that soon.

Nic said...

Wow that looks delicious:)
Do you mix the cauliflower into the paella before serving or serve it on the side?

Anonymous said...

Wow ... as a new Paleo person (just passed the 30-day mark) and an expat living in Barcelona, this is a double bonus post for me! I'll keep tuned for more ...

Bring it on!


Post a Comment