Do you have a pressure cooker? If you do, this recipe is done in less than an hour. If you don’t, it’s okay – you can still make this recipe. Just follow the instructions until it talks about the pressure cooker timing and either cook it on the stove top or in the oven for 2-3 hours until your meat is tender. Whichever cooking method you choose, the flavors in this recipe are rich and hearty, just perfect for a cold winter day.
Beef Stroganoff has been around for 150 years or so. It has stood the test of time for sure, sometimes disappearing for a while but always coming back into vogue. For most of its history, however, noodles were the base. Not so in the paleo world – here it’s all about zoodles! I quickly steamed my zucchini noodles for this recipe because they don’t need any flavor other than their own. All the deep, complex deliciousness comes from the beef and mushrooms.
If you’re short on time, break out the pressure cooker. If it’s a lazy weekend, you can let this simmer and fill the house with its wonderful aroma while celebrating the simple pleasures of the season!
Paleo Beef Stroganoff
1 lb. stew beef, cut into 1 in. chunks
3 tsp. coconut oil, divided
1/2 tsp. + 1/4 tsp. salt
1/4 tsp. pepper
1/4 tsp. garlic powder
1 medium onion
8 oz. baby portabello mushrooms, thickly sliced
3 cloves of garlic, crushed
1/2 tsp. paprika
1/4 tsp. dried thyme
1/4 tsp. onion powder
2/3 c. beef broth
1/2 c. full fat coconut milk
1 Tbsp. parsley, chopped
Directions
1) Coat the beef with 1/2 tsp. salt, pepper, and garlic powder. Use your hands to rub it all over the meat and set aside for a few minutes. Melt 2 tsp. coconut oil in a pressure cooker over medium-high heat. Allow the oil to get nice and hot and then brown the beef on all sides. This is best done in batches to avoid steaming the meat. It takes about 4 minutes per batch, adding additional oil as necessary. Remove each batch of browned beef to a bowl to catch any juices.
2) Add onion, mushrooms, and 1/4 tsp. salt to the pot, stirring to scrape up any browned bits. Cook until slightly caramelized, about 10 minutes.
3) Return the meat to the pot with the mushrooms and onion, add the garlic, paprika, thyme, and onion powder and stir to coat everything. Add the beef broth to the pot, close and seal the pressure cooker lid, and bring it to a boil. Reduce the heat to the point where the pressure cooker top is gently, but steadily, rocking (for me this is just below medium on my stove). Keep at this steady pressure for 15 minutes and then remove the pot from the heat. Allow the pressure to dissipate on its own, which should take about 10 minutes.
4) Remove the lid, add the coconut milk, and simmer over medium-high until the sauce reduces and thickens slightly. Serve over zucchini noodles (below) with a sprinkle of parsley.
Steamed Zucchini Noodles
3 medium zucchini
salt
Directions
1) Cut the tops and bottoms off your zucchini. If you have a spiral slicer, use the flat blade to create these beautiful thick ribbons. If you have a julienne peeler or are using a knife, slice your zucchini into long strands.
2) Place the zucchini in a strainer over the sink and sprinkle liberally with salt. Let rest for about 20 minutes to allow some of the moisture to be pulled out of the zucchini.
3) When you are ready to eat, rinse the zucchini well and steam for about 2 minutes. I used my steamer bowl in the microwave, but you can use whatever you have. We just want the zucchini lightly steamed, not mushy.
4) Place in a bowl or on a plate and top with the Beef Stroganoff. Enjoy!
Serves 2-3
Balancing Paleo 
this looks great!! i always loved stroganoff in my pre paleo days. it was filled with sour cream and we ate it with egg noodles. so delicious. i will have to try your lighter version.
I hope you like it, Joanna! While zucchini noodles aren’t the same as egg noodles, I like them just as much. Let me know what you think!
Pingback: Sydney Bakers Recipe used in his Restaurant Sydney’s : Beef Stroganoff | Stephen Darori on Family Recipes and Cooking
I was skeptical, but this turned out amazing. I’m glad I doubled the recipe. Used the Dutch oven stove method. Yes it took a while, but all I had to do is just stir it a few times. Thanks for such a great recipe
You are so welcome! And thank you for commenting about it – I really appreciate it!
Oh and the zucchini noodles worked perfect with it. Was the first time using my spirooli.
Love it!
Made this dish tonight for the hubby that is a bit of a food snob when it comes to paleo 🙂 he loved it! Thanks for sharing!!!
I am so glad!!! I have a beef stew recipe coming that is really good too! I forgot to take pictures and my husband and son cheered because it means I need to make it again soon. 🙂
I made this last night for my parents, I made a double batch hoping it would be enough to have leftovers. I am happy to say they loved it and we have no left over. Thank you for all the recipe ideas. Makes eating so much fun.
I’m so glad you all enjoyed it! We have trouble saving some for leftovers too. 🙂
Made this last night with some leftover eye of round. Browning the meat ahead of time provided a rich, delicious flavor. I was worried the coconut milk would overpower the dish, but it worked beautifully! The sauce was amazing – think, creamy, and delicious. My husband and I literally licked our plates. This will be a frequent go-to recipe from now on. Thanks so much!!
I love it!! And there is never, ever anything wrong with licking your plate!! 🙂
This recipe has become a staple in our kitchen for a quick weeknight meal. Easy, straightforward and delicious everytime! I like to beef it up (pun intended) with extra veggies. Thanks for a great recipe!
Thank you so much for letting me know! I am thrilled that you love this recipe as much as we do!
Served this over creamed cauliflower and it is soooo good. My 3 boys devoured it and there are sadly no leftovers. Oh, I left out the paprika because I am AIP.
Over creamed cauliflower sounds delicious! I am glad you all enjoyed it and that you made it AIP friendly. Brilliant!
What would be a good cut of beef (I’m pretty clueless when it comes to cuts of beef) to use? Are there different cuts that would qualify as “stew meat”? Thank you, in advance!
You could use a chuck roast and cut it into 1 inch pieces and it should work great!
Could this be made in a crock pot, after searing my meat on all sides, on the stove top?
I’m sure you could but you would probably need to cut back on the liquid, maybe just a quarter cup of broth. You might wait until the last hour to add the coconut milk and adjust the amount depending on how much liquid the beef and mushrooms released during cooking.
Let me know how it works out if you do!
Vanessa, I’m curious to know if you tried the recipe in the crockpot? I made this for the first time a couple weeks ago and it was a BIG hit! Would love to be able to make it even easier, as we have so many activities in the evenings and I am finding it difficult to feed my family healthy, quick meals. Thanks!
Looks like we need a slow cooker version. And maybe a few other recipes in the SC too!
Pingback: Too Busy to Eat Healthy? | Balancing Paleo
I made this last night. I tripled the recipe, used two pounds of mushrooms (one lb crimini, one lb shitaki). I cooked it in a dutch oven (in the oven) at 400 degrees for about 3 hours.
Absolutely amazing. Thanks for the recipe.
Fantastic, Adam! I am so glad!
This is so delicious! I forgot to buy mushrooms but went ahead regardless and I loved this meal. I also omitted paprika to make this AIP and all I can say is yum! Thank you so much!
I’m thrilled you liked it, Amy! I’m actually working on a slow cooker version as well which I’ll be posting soon.
Pingback: Slow Cooker Beef Stroganoff | Balancing Paleo
we’ve featured this recipe on our vegetable noodlemaker fanpage (with a link back here, naturally), and our fans loves it!
Thank you! I’m so glad they love it!