My Heart Beets

Home > Meat & Protein > Beef

Paleo Beef Stroganoff

122 Comments

Jump to Recipe
Paleo Beef Stroganoff by Ashley of MyHeartBeets.com

This is the best beef stroganoff I’ve ever eaten – paleo or not. This is my grown-up take on a childhood classic – it’s a little spicy, rich, and extremely comforting.

When I paleo-ify a recipe, and it turns out better than the original version, I honestly count my lucky stars. I have no idea how this recipe turned out as well as it did, but trust me, it’s phenomenal. The sauce = insanely delicious. You won’t even know it’s “paleo.”

I think the secret to making good food comes down to the quality of ingredients used. This recipe only calls for only a handful of ingredients – but the quality of those few ingredients makes all the difference.

“Holy heck, this recipe is fantastic! Gluten free, dairy free, and tastes better than any of standard stroganoff recipes I’ve tried, restaurants included.”

Jen
Paleo Beef Stroganoff by Ashley of MyHeartBeets.com

The main ingredients you’ll need to make this recipe:

  • Stew meat
  • Bone broth (or stock),
  • Dijon mustard (I love Sir Kensington’s mustard – I buy mine at Whole Foods)
  • Ghee or butter
  • Worcestershire sauce
  • Baby portobello mushrooms
  • A few spices

One of those spices: freshly cracked black pepper. It may be a humble spice, but it takes this creamy sauce to another level. The fresh black pepper and cayenne elevate this dish to more of an “adult” recipe. You can decrease those two spices if making this for kiddos.

My recipe doesn’t call for any wine, and I don’t think it needs it – but feel free to add a splash of white if you want. The brand of Dijon I use actually has a touch of chablis wine in it.

This recipe is traditionally made with sour cream or cream, but I use coconut cream to keep my recipe lactose and casein-free. You won’t notice the coconut flavor – truly! The slight hint of sweetness that the cream brings really complements the slight heat from the spices.

This recipe doesn’t call for any special type of thickener. You don’t need it. Just keep reducing the sauce until it reaches your desired consistency – doing this will not only make for tender beef, it’ll also concentrate the flavors and create a thick, rich, noodle-coating sauce.

I highly suggest serving this dish overtop (paleo-friendly) noodles. I like this brand (most Whole Foods stores carry it in the freezer section for about $8). I think the noodles really make this feel like such a treat!

Paleo Beef Stroganoff by Ashley of MyHeartBeets.com

Paleo Beef Stroganoff

Paleo Beef Stroganoff by Ashley of MyHeartBeets.com

Paleo Beef Stroganoff

4.95 from 39 reviews
Pin Recipe Print Recipe

Ingredients
 

  • 3 tablespoons ghee or grassfed butter
  • 1 pound beef stew meat
  • 1 teaspoon salt
  • 1 teaspoon freshly cracked black pepper
  • 1 teaspoon onion powder
  • 1 teaspoons garlic powder
  • ½ teaspoon cayenne
  • 1 onion finely diced
  • 4 cloves garlic minced
  • 1 tablespoon worcestershire sauce
  • 2 teaspoons dijon mustard
  • 1 ½ cups bone broth

Add Later:

  • 1 6 ounce package of portabello mushrooms, sliced
  • ½ cup coconut cream put canned full fat Coconut Milk in the fridge overnight, use the cream on top

Serve with

  • Paleo Pasta you can find this at Whole Foods for around $8

Instructions
 

  • Melt the butter in a dutch oven or heavy pot over medium heat.
  • Add the beef and spices and brown the beef on all sides for 2 minutes. Reduce the heat to medium-low and continue to brown for another 5 minutes.
  • Next, add the onions and garlic. Saute for a minute, then add all of the remaining ingredients except for the mushrooms and coconut milk.
  • Bring the broth to a boil, then reduce the heat to low and cover the pot. Cook for 45 minutes or until the beef is tender.
  • Remove the lid, stir in the mushrooms and coconut cream. Increase the heat to medium, then cover and cook for 10 minutes.
  • Remove the lid, bring the sauce to a boil and reduce until the sauce reaches your desired consistency.
  • Serve over paleo pasta, rice or baked potatoes, if desired. (you can find the pasta at Whole Foods for ~$8 in the freezer section).
Did you make this recipe?Tag @myheartbeets on Instagram and hashtag it #myheartbeets!

Pin This Recipe

Like this recipe? Pin it to your favorite Pinterest board now so you will remember to make it later!

Pin Recipe Now0

Related Recipes

Cookbooks

Find out more about my cookbooks Indian Food Under Pressure and South Asian Persuasion.

See My Cookbooks

About Ashley

Hi, I’m Ashley. Thanks for being here! I truly believe that food brings us closer together. Gather around a table with good food and good people, and you’ll have the ingredients you need to create some happy memories. My hope is that you find recipes here that you can’t wait to share with family and friends.

Meet Ashley

Subscribe

Subscribe to get our latest content by email. We won't send you spam. You can unsubscribe at any time.

Reader Interactions

Leave a Comment & Rating

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

Recipe Rating




Comments

  1. Jess says

    5 stars
    Wow! This is by far the best tasting stroganoff sauce I’ve had. It is definitely a keeper the flavor was just amazing. I did modify mine. I don’t like a lot of heat so I did an 1/8th tsp of cayenne and 1/4 tsp pepper. The one issue I had was that it didn’t thicken so we added a flour/cold water slurry and that helped. Thanks so much for a delicious recipe!

    Reply

  2. Mike says

    4 stars
    My wife and I made this earlier this week and loved the flavor! Reducing the review by one star to 4/5 though because even though we followed the measurements to the letter, we had hardly any leftovers after each of us only had one basic serving.

    I’m thinking of doubling everything so that we have a true amount of leftovers (at least 4 servings)…maybe that can be added to this recipe? I swear we used the exact amounts called for here but we were so surprised that we had (maybe) a cup’s worth of stroganoff remaining. Very tasty, though!

    Reply

  4. Meagan Sellers says

    A friend of mine had made this and it was delicious, so I wanted to make it myself. I decided to try to make in in my Instant Pot. I clicked “sauté” and melted the butter and browned the stew meat and spices (I skipped the cayenne because my mom can’t handle heat,) added the onion and garlic and let those sauté for a minute. Instead of Worcester’s sauce, I poured in a little bit of Primal Kitchen’s Steak Sauce and a little coconut aminos. I added in everything else except the coconut cream (I skipped the mushrooms as we aren’t fans lol,) put on the lid, and hit “Meat/Stew” and set it for 35 minutes. I did a quick release and thankfully, the meat was pretty tender by that point. I added in the coconut cream, clicked “Sauté” again and let it boil for maybe 10ish minutes. Once that was done, I set the temperature to “Less” and let it reduce until I liked the consistency. I did add a slurry of arrowroot powder and water to help thicken it up. I ate it with rice, and it was delicious.

    Reply

  5. Alison Oliver Fell says

    Do you know about how much onion by weight or cup? Sometimes the onions I can buy are giant and sometimes they are very small. Thank you!!

    Reply

  6. Joy says

    5 stars
    My husband really enjoys this. I don’t have Worcestershire sauce so I use balsamic and coconut aminos, and omit the pepper.

    Reply

  7. Julie says

    Oh, thank you!!!!! This was so good, my husband who normally cringes when I prepare “imitation” dishes declared, “10 stars! Let’s have it again…soon.” SCORE!!!!!!

    Reply

  8. Jen says

    5 stars
    Holy heck, this recipe is fantastic! Gluten free, dairy free, and tastes better than any of standard stroganoff recipes I’ve tried, restaurants included. I did swap the coconut cream for homemade coconut yogurt to give it a little tang and added a splash of marsala wine, but the base recipe is great as-is. Definitely five stars!

    Reply

  9. jeff says

    4 stars
    Really liked it. Used zucchini and summer squash noodles instead of paleo pasta. Would cook the noodles separately next time to get rid of some of the liquid. Would do it again.

    Reply

  11. noelle says

    Hi Ashley,
    First off, I have say I love every recipe of yours that I’ve tried!!
    Just wondering how you would convert this one to the IP.
    Much thanks,
    Noelle

    Reply

  12. Roxanne says

    5 stars
    This recipe is absolutely delish, Ashley! You have outdone yourself with the perfect blend of savory meat, flavorful mushrooms and gravy with a little kick to it. My husband loved it, too. I will be making it again soon. It’s better than my original sour cream recipe and I am SO overjoyed to have a paleo recipe better than my yummy original. Wow, wow, wow!

    Reply

  13. Melissa says

    I don’t know if I’ve ever left a recipe review before, but I just had to with this one! This was DELICIOUS. I made it with venison instead of beef and it was super yummy. I thought the coconut milk was going to be a poor flavor match but I was surprised! I tasted zero coconut. Thanks for the great recipe!

    Reply

  15. Annette says

    5 stars
    This is delicious! The sauce was very rich and not coco nutty at all. I served mine over cauliflower mash and my husbands over egg noodles. I have a quarter cow to use up and this was a great way to use a tough round steak

    Reply

  16. Emily L. says

    5 stars
    I’m back to make this recipe a second time because my husband and I thought it was just so. darn. delicious. This one really hits the comfort food spot without any of those comfort food ingredients that leave us feeling yucky and bloated. Thanks for this gem (and a new family favorite).

    Reply

  18. Janet says

    5 stars
    I was looking for a paleo recipe for stroganoff to use some of our venison and some gluten free egg noodles I found at the grocery. This recipe came up and is the first recipe I tried from your site. I will definitely be back for more. After reading the recipe and most of the comments, I tried the arrowroot technique someone suggested. I did it in my instant pot after finding someone’s suggestion for cook time. I HATE the taste of coconut, so have been reluctant to try it in recipes, but decided to go for it this time after someone commented they also disliked it and couldn’t taste it. They were right! I couldn’t taste it at all. In fact, I found that the cream didn’t even smell of coconut, just the water left over. I also halved the cayenne as someone else suggested, which was a good call–it had plenty of bite for us with the lesser quantity! Next time I will use more meat. I am the one with diet restrictions, so my husband doesn’t often eat the same things I do, but he joined me for this meal. My husband LOVED it (me too) and as we were eating, he said, “I can really taste the sour cream” — HAHAHA. I so enjoyed telling him I didn’t use any!! He said this recipe is definitely a keeper!

    Reply

    • My Heart Beets says

      LOL that he said he could taste the sour cream!! That literally made me laugh out loud! That’s so awesome – I’m so glad you guys liked it! Thanks for letting me know how it turned out!

      Reply

  19. Steph says

    Thank you… Just made this tonight with some modifications to fit my family’s needs and it was a hit, everyone loved it. So delicious. Love it when I find something everyone will gladly eat. It taste similar to my mom’s recipe with ingredients I can eat

    Reply

  20. Deirdre says

    So looking forward to making this. I’m going to use beef tenderloin or sirloin what do you think the cooking time would be ? Don’t want to overcook.

    Reply

  22. Beth says

    Love this recipe. So delicious and wholesome. I added a little bit of tapioca starch and parsley at the end just for thickness and because I love parsley. This recipe is definitely a winner at my house.

    Reply

  23. Stephanie says

    5 stars
    This dish was amazing! Followed the recipe exactly except I used normal cream. Turned out amazing. One of my favourite recipes ever!

    Reply

  26. K.Smith says

    I loved this dish! I made it while doing the Whole 30, and it is a keeper. Served it over mashed cauliflower. Delicious! Thank you

    Reply

  27. Tracey says

    5 stars
    I’m new to paleo so was looking for some recipes that weren’t too bland and could be a weekend treat. In the words of my partner, “this was one of nicest meals I’ve ever had, restaurant quality!”. I served it with cauliflower mash and veg and it’s safe to say this will be a regular in my house. Thank you so much!

    Reply

  28. Amy says

    I have been experimenting with different paleo recipes and this is by far one of my favorites! I made it yesterday and have been looking forward to dinner all day 🙂 I

    Reply

  30. Beth says

    5 stars
    Loved this recipe. My mom used to make beef stroganoff when I was growing up, and this was way better (not to mention way healthier)! I loved the expensive Paleo noodles, but going forward, I would use Trader Joe’s cauliflower gnocchi because it’s only $3 instead of $8.99 like the Whole Foods noodles.

    Reply

    • My Heart Beets says

      Beth, so happy to hear that! 🙂 Trader Joes is awesome for gf items! Great tip about the cauli gnocci! TJs also has gluten free fettuccine noodles in their refrigerated section and they are delicious – I haven’t tried them in this particular recipe just yet but I am sure they’d be just as good as the paleo noodles!

      Reply

  32. Lori says

    5 stars
    Oh my, this was amazing. I also cooked it in the crock pot after browning the beef. I will be making zoodles and butter nut squash noodles, as well as shirataki noodles to try it with.

    Reply

  33. Vivienne says

    5 stars
    Our family has always loved Beef Stroganoff, so with starting Paleo I was in search of a replacement. I made this tonight and my family loved it. They said it was better than the non paleo one. Our 18 year old daughter informed me it was one of her 3 favourite meals. Thank you for sharing this recipe

    Reply

  34. Marce says

    5 stars
    Great!!!! I used shitaki mushroom and shitaki noodle…. was delicious 😋 my family reported: can I eat more????? Thanks

    Reply

  35. Anne says

    I’m wondering if this could be done with chicken breasts or thighs and if that would change the cooking time? Thank you!

    Reply

    • My Heart Beets says

      Hi Anne, that sounds intriguing! I haven’t tried with chicken but if you use chicken breasts then you’d definitely want to reduce the cook time. Let me know what you think if you try it this way!

      Reply

  36. Melissa Hart says

    I made this when I found out I couldn’t eat dairy anymore while breastfeeding my son who had a dairy intolerance. My husband and I love it so much that it stays in our weekly rotation even if I can eat dairy again! Thank you so much!

    Reply

  37. Robert Paul says

    5 stars
    We’ve made this recipe half a dozen times so far I think. I can eat pasta while my wife has zuc noodles with hers. An awesome stroganoff recipe that will stay in our house. We like heat (spicy) as well but if you don’t, the last batch we made with half the cayenne and it was still plenty. Also we substituted half a container of lactose free sour cream instead of coconut cream this time. It works just fine.

    Reply

    • My Heart Beets says

      Robert, that’s so great to hear! I’m glad you and your wife like this 🙂 And thanks for sharing that info about using sour cream instead of coconut cream – that will definitely help others looking to make this!

      Reply

  38. Danielle says

    5 stars
    Sooo good!!!! I love an indulgent recipe that I don’t feel guilty about afterwards, ha!
    Next time, I would reduce the cayenne because I’m a giant baby and it was almost too much to get through my bowl, but seriously, awesome dish!!!

    Reply

  39. Christina says

    5 stars
    Incredibly delicious! A note to those wondering about the coconut cream: can’t taste it at all. My husband hates coconut, and he didn’t even know this had coconut cream in it. I will definitely make this again.

    Reply

  40. Sarah Thacker says

    5 stars
    Thanks for this recipe! My husband loves it (I do too) and said he thinks it’s just as good as the one at Noodles and Company but unlike theirs, he doesn’t feel bad after eating it. It was a little spicier than we expected, so I might reduce the cayenne in the future. Definitely look forward to making it again!

    Reply

  44. Christine Piggott says

    5 stars
    Made this last night as am on a mission to find new recipes and also try paleo eating. This was delicious and my husband loved it ( he doesn’t know it is a paleo recipe). I thought the coconut was going to taste as I thought it smelt quite strong when I added it but I couldn’t taste it at all. I left out the mustard, added some white wine and forgot to buy worcestershire sauce so added HP sauce instead which seemed to work fine! Not a fan of the paleo pasta, tasted a bit too much like uncooked pastry for my liking but it’s ok in small doses and mixed in to the stroganoff. Will definitely be making this again.

    Reply

  45. Jennifer says

    5 stars
    I just wanted to say that this is one of my all-time favorite beef stroganoffs. I’m not sure why more recipes don’t call for mushrooms, at least as an optional ingredient, because it takes the flavor profile to a new level. I was also hesitant about the mustard, but am so glad for it as it’s very subtle and I feel helps make up for potential flavor loss from the alcohol a lot of recipes call for. I’ve made this about 4 times now at the request of my picky husband, and am usually pressed for time so once the meat is browned, I throw everything into my Instant Pot for about 20 minutes, minus the mushrooms and coconut cream. This also allows me to use cheaper cuts of meat, so I typically make this with a roast.

    To save money on coconut cream/ butter/ etc., I purchased a 20pound bag of coconut manna on Amazon for just over $20, melt it down in a big stock pot to combine, and then freeze in smaller mason jars. Then I just take a heaping spoonful of coconut butter and a cup or 2 of water and run in the blender for a minute, and throw through a fine mesh strainer in a mason jar for the equivalent of canned coconut milk. The coconut cream works in the same way, where I’d put the jar of coconut milk in the fridge overnight to separate and the stuff at the top is a perfectly smooth and creamy coconut cream, for pennies on the dollar. Anywho, thank you for a keeper of a recipe. It’s decadent and would and has, impressed even my SAD-eating friends and family.

    Reply

  46. Aliene says

    This looks so delicious! Question – the ingredients say “onion powder and garlic powder” but instructions say “Saute onions and garlic”. Do we use fresh or powdered?

    Reply

    • My Heart Beets says

      Hi Ailene, if you look at the ingredients underneath the spices listed you’ll also see the recipe also calls for 1 onion and 4 cloves of garlic. Hope that helps! Let me know if you try this 🙂

      Reply

  47. Tiffani says

    5 stars
    I adore this recipe! I’ve made it with beef, lamb, and also venison and it works deliciously with all 3 meats. I would give this 6 stars if I could!!

    Reply

  48. Carrie says

    Is there something you could use other than worcestershire sauce? I can’t have gluten or soy and this looks so good.

    Reply

  49. Farrah Geroso says

    This recipe is delicious! Thanks for another great one Ashley. I did double the recipe and made it in a crockpot. I took the advice of Keri for the cooking time and adding the coconut cream and mushrooms in the last 30 minutes of cooking time. The second time making this, I coated the meat in arrowroot powder first, before browning. I also took about 4 tbsp of butter after browning and got all the bits off and added about 2 tablespoons of arrowroot and made a quick roux then added the cooking liquid to make a thicker sauce. I whisked it all up before adding it to the crockpot with my spices. It turned out very delicious and gave a thicker sauce that I was looking for. I did add 33oz of broth since I doubled the recipe and thickened the sauce. I served it on top of cauliflower mash. Thanks again for a great recipe.

    Reply

  50. Maryna says

    This was so tasty!! Just amazing. Me and my husband both loved it. Will be definitely using this recipe over again. Thanks!

    Reply

  51. Keri says

    5 stars
    We tried this last night and I was kinda shocked at how good it turned out! You definitely could not taste the coconut flavor at all. I made it in the crockpot (browned the meat, everything in the crock except coconut cream and mushrooms 4 hrs on high, coco and mush in at last 30) and served over Cauliflower Mash and it was a hit! My carboholic husband said it was so good that didn’t even miss his beloved pasta with it! Thanks for the great recipe!

    Reply

      • Crystal P. says

        Why have I never thought of that? I usually use broth over water, but now I plan to use this. As always, thank you! I have not made anything from your page that the whole family did not love. Your recipes have an integral place in the cooking rotation! Tonight, I’ll make this one for the first time. I already know it’ll be a hit!

        Reply

  54. Miriam says

    looks like a terrific recipe and I am planning to make it next week. I didn’t see anywhere how many servings you think it would make. Can you add that to your recipe format?

    Reply

    • My Heart Beets says

      Hi Miriam, thank you! I hate writing the number of servings because I’m not a nutritionist and have no idea what “proper” portion sizes are – but if I had to guess I’d say that it would feed 3-4 people.

      Reply

      • Hailey says

        Heehee depends how hungry you are😜.
        My roommate and I had this and it made 3 good dinner and 2 leftover for packed lunch sizes. We are little but, can pack this one away with ease.

        Reply

  56. Lynn says

    Instead of doing the trick with the can of coconut milk to get the “cream,” could I just use coconut cream concentrate? I’ve had a jar of it sitting around, but I’ve never been quite sure how to use it!

    Reply

    • My Heart Beets says

      Lynn, coconut cream concentrate is coconut butter (to my knowledge) which is different from coconut cream. Coconut butter is very thick… I know Trader Joe’s sells canned coconut cream which is easier than the “coconut milk trick” 🙂

      Reply

      • Karin says

        5 stars
        Hey Ashley-

        I got a shipment of ‘thin slliced beef’ from Buther Box and I didn’t know what to do with it as it is shaved very thin. I searched for ‘paleo beef stroganoff’ and your recipe popped up. It was soooo delicious! Also I had no idea about the paleo pasta until you mentioned it..headed straight to whole foods to get it. it’s the.first paleo pasta I’ve tried that was truly delicious!!! nice work! My only constructive comment is that you mention a package of sliced portabella mushrooms, which I added as is. The mushroom slices of a portabella mushroom are too big for this recipe in my opinion. I suggest modifiying to state you can use any sliced mushrooms you want as any of them would be delicious in this recipe. Even chatarelles, which are more peppery, would be great. I love your blog and I find that of all the paleo websites I tend to use for recipes, yours is the one I keep coming back to!!! thank you

        Reply

  57. Ragna says

    That was AMAZING! Loved it. The noodles, though somewhat expensive, really help make this extra special. Better beed stroganoff than I have had anywhere.

    Reply
paneer lababdar

Ashley's Secrets

INDIAN FOOD

MADE EASY

Favorite tips & tricks to

easy & delicious Indian cooking

FREE EMAIL BONUS