Cinco de Mayo Paleo Recipe Roundup

Before paleo, Cinco de Mayo was a damn fine excuse to knock back a bunch of margaritas and eat my way through baskets of tortilla chips like a locust with something to prove.

Sigh. There’s no more of that.

But that doesn’t mean we can’t commemorate the Mexican army’s 1862 victory over France during the Franco-Mexican War (YAY, history!) with crazy-good food. It just means we have to celebrate the Battle of Puebla with appropriately paleo crazy-good food.

Really, you could just crack open an avocado, grab a spoon, and call it good. But if you want something a little more involved, here are some favorites from my recipe archive, plus a few bonus recipes from some of my paleo pals. You have plenty of time to hit the store tonight or tomorrow, so you can whip up something with the right amount of vavoom for Cinco de Mayo on Saturday. Viva México!

Machacado and Eggs
Eggs scrambled with dried beef, tomatoes, jalapenos, and a hint of chili powder

Mexican Meatza
Meat crust, creamy avocado, tangy salsa… who needs cheese?!

Stoveop Pork Carnitas
Fall-apart tender. Might replace bacon as your favorite use of pig.

Tropical Chopped Salad
Creamy, cool, and luscious with avocado, red pepper, shrimp, and mango

Fiesta Tuna Salad
Liven up lunch!

Spiced Cantaloupe
Coarse salt and a little paprika mean big, bold flavors

More From Paleo Friends

You might also like these recipes from my other favorite paleo foodies.

Nom Nom Paleo’s Oven-Braised Mexican Beef
Nom Nom Paleo’s Overnight Oven-Braised Shredded Pork Tacos

Mexican recipes on the fabulous Chowstalker

Mexican recipes on the equally-fabulous The Foodee Project

The Food Lover’s Kitchen Cinco de Mayo Menu
… includes salsa, guacamole, steak fajitas, tacos with jicama shells, and taco salad

Everyday Paleo’s Seafood “Enchiladas”

And if you want a gluten-free, grain-free treat…
Paleo Parents’ Mexican Chocolate and Vanilla Bean Whoopie Pies

Oven-Fried Potato Latkes (Paleo)

In each issue of Paleo Magazine, I team up with Steph Gaudreau to bring you the story of a traditional recipe and adapt it to fit into a...

Read More
25 Amazing Paleo & Whole30 Recipes for Thanksgiving

Thanksgiving has always been and remains my favorite holiday. We don't always go the traditional route. For example, there was the year we ate Elvis...

Read More


  • Justin Ross says:

    Wait, why isn’t your fantastic, simple stovetop carnitas recipe on this list? It’s just so good!

    Making it tonight for a work pot luck, even. 🙂

  • Melissa says:

    “like a locust with something to prove” – love it! For me, it is sometimes more “like the fate of the world depended on it”…why I try not to have that stuff in the house 🙂 Jicama is such a good sub (but it’s not the same if you are confronted with a basket/bag of chips). I like the lettuce/jicama taco wrap idea – I have found purple cabbage leaves make a great wrap for grilled chicken piece w/ veggies and a drizzle of hummus, guac or oil if desired.

  • I still haven’t tried the “meatza” yet. I need to put it on my list. The boys go nuts for meat muffins, I bet that would be a winner!

  • AndreAnna says:

    Yesssssssssssss! I’m having a Paleo Cinco de Mayo party on Saturday and this is great! (I’m fairly certain that Mexican food is like the easiest to make Paleo)

  • Hi! We always have Machacado Con Huevo when we’re down in Cabo and oddly enough I’ve never really thought about making it here but then again I have never seen Carne Seca in grocery stores. My husband does make scrambled eggs with Biltong sometimes (rarely) and it is so delish. Biltong is a South African version of dried meat. Salty and spicy like carne seca but generally thicker, chunkier pieces when sliced. Might have to put in some effort to whip these up for the occasion. My favorite thing about Mexican though is hands down Guacamole!

    Happy Cinco Weekend!

    • Mel says:

      Oooh, I want to try Biltong. Where do you get it?

      • My husband makes it – we use grass fed London broil, a home blend of spices and his a ‘dryer’ he built. We’re planning on doing a how-to video sometimes soon so I’ll let you know. I think there are some online sources – or there were a while ago. Its easy to make though and most of the ones we saw to buy had MSG in the spices they ysed.

  • Pingback: 5/4/12
  • Wally Trawinski says:

    I know what you mean about the corn chips! And I just love guacamole – but what to do with it? So today I am making some crackers with almond flour. I will also be making some coconut flour tortillas.

  • Marie says:

    oh my! I just made a complete whole30 approved mothers day lunch for my family and they loved it! we had your pork carnitas wrapped in butter leaf lettuce and drizzled with cumin-like dressing, homemade guacamole and salsa, tropical chopped salad and sunshine sauce with celery and peppers for dipping as an app. AND my husband bought me Well Fed for mothers day! it was all perfect!! thank you for your beautiful, tasty food!

    • Mel says:

      YAY! Happy Mother’s Day! I love that you had a Whole30 celebration. Your menu sounds delicious. Congratulations — and thank you so much for letting me know.

  • Amelia C. says:

    I’m a little late but I’m Chicana so I think I can suggest other stuff. (I don’t cook though, I’m suggesting things my mom has cooked >_> )

    -Ceviche (Fish or shrimp. I don’t know what you would eat it on since we usually eat it on tostadas. I would just eat it with a spoon)


    -Some eggs in salsa (my mom makes large batches of salsa because we eat it with everything; when we have leftover salsa we put it in a skillet and poach some eggs in it *drool*)



    -Camarones (shrimp): a la diabla, al mojo de ajo, and rancheros

    -Coctel de Camaron

    -Nopales con Huevo (cactus and eggs)

    -Tacos de lengua (beef tongue tacos [with lettuce leaves instead of tortillas)

    -Picadillo (use sweet potatoes instead of regular potatoes)

    -Fajitas (my mom has never made these but I’ve eaten them at restaurants)

    -Chiles rellenos (stuff with meat and veggies instead of cheese and don’t add flour at the end)

    The way my mom cooks some of these things aren’t paleo but they can be adapted

  • Pingback: happy weekend!
  • Marnie says:

    Melissa! I lent my copy Well Fed to my best friend for a bit of time and am preparing Machado con Huevos for a brunch tomorrow morning. I remember the book including a recipe with an avocado concoction… any chance you could share that with me so I don’t have to stalk by best friend who’s busy with newborn twins and a 3 year old?!?

    • Here you go. Enjoy!

      Avocado Relish:
      1/2 avocado, cut into 1/2-inch dice (about 1/2 cup)
      1/4 cup cilantro leaves, minced (about 1 tablespoon)
      1/4 medium red onion, minced (about 2 tablespoons)
      2 teaspoons fresh lime juice (about 1/2 a lime)
      salt and black pepper, to taste

      Place all the ingredients for the avocado relish in a small bowl and mix gently with a fork until just combined; you want the avocado to retain its structural integrity. Set aside to allow the flavors to meld while you make the eggs.