Broccoli Cheddar Stuffed Baked Potatoes

$6.76 recipe / $1.69 serving
by Beth - Budget Bytes
4.59 from 31 votes
Pin RecipeJump to recipe →

This post contains some affiliate links, which means that we make a small commission off items you purchase at no additional cost to you.

These Broccoli Cheddar Stuffed Potatoes might not be the prettiest things in the world, but who cares? We’re talking about CHEESE AND POTATOES. Plus a healthy dose of broccoli, because life is all about balance. These Broccoli Cheddar Baked Potatoes are, IMHO, the perfect half way point between comfort food and good-for-you food. And I like compromise.

Two broccoli cheddar stuffed potatoes, each in an individual white casserole dish

What Else Can I Add to My Stuffed Potato?

This is yet another great “base” recipe that you can customize to fit your wallet and taste buds. The original version posted below is so good that it made my feet wiggle, but if you want to add more, here are a few fun things you can add in or on top:

  • bacon bits
  • grilled chicken
  • jalapeños
  • sriracha
  • sliced ham
  • sliced green onion

Empty out the fridge and use up leftover ingredients as toppings. Anything that is good on a loaded baked potato would probably also be good on these, so that might give you a place to start experimenting.

How to Add More Flavor to Cheese Sauce

The cheese sauce in this recipe is a fairly mild and creamy cheese sauce, so if you like a cheese sauce with a little more punch, I’ve got some options for you. To add “tang” to the cheese sauce, you can add a ½ tsp Dijon mustard, or ½ tsp mustard powder. To add tang AND heat, try adding a few dashes of your favorite hot sauce. Or you can go the black pepper route and add a hefty dose of freshly cracked pepper. 

Meal Prep It!

These Broccoli Cheddar Stuffed Baked Potatoes reheat really well in the microwave. I just reheated one for second breakfast and it was AWESOME. (“Second Breakfast” is to early birds what “fourth meal” is to you night owls). So make a whole batch and pack them up for your lunches throughout the week!

How to Save Money on Cheese

Always check the prices of larger blocks of cheese compared to the smaller blocks. At my local store they’re almost always just about the same price per ounce, but this week the large 16oz. block was only $3.88, which is a GREAT deal. The large block can be cut into smaller chunks and stashed in the freezer. Just make sure to wrap them tightly to prevent freezer burn.

Choose Block Cheese Instead of Pre-Shredded

For this recipe and any cheese sauce recipe, try to get cheese in a block and shred it yourself. Pre-shredded cheese is usually coated in an anti-caking powder that can prevent it from melting nicely into the sauce.

A fork digging into a broccoli cheddar stuffed potato

Love stuffed baked potatoes? Check out the long list of baked potato topping ideas in How to Make Baked Potatoes!

Share this recipe

Broccoli Cheddar Stuffed Baked Potatoes

4.59 from 31 votes
Broccoli Cheddar Stuffed Potatoes are a vegetarian comfort food classic. Perfectly baked russet potatoes with a rich and creamy broccoli cheese sauce!
A fork digging into a broccoli cheddar stuffed potato
Servings 4
Prep 10 minutes
Cook 1 hour
Total 1 hour 10 minutes

Ingredients

BAKED POTATOES

  • 4 russet potatoes (about ¾ lb. each) ($2.35)
  • 1 Tbsp olive oil ($0.16)
  • Salt ($0.02)

BROCCOLI CHEESE SAUCE

  • 1/2 lb frozen broccoli florets ($1.19)
  • 3 Tbsp butter ($0.39)
  • 3 Tbsp all-purpose flour ($0.03)
  • 3 cups whole milk ($1.27)
  • 1 tsp salt ($0.05)
  • 1/4 tsp garlic powder ($0.02)
  • 6 oz. medium cheddar, shredded ($1.28)
Email Me This Recipe
Get this sent to your inbox, plus get new recipes from us every week!
Please enable JavaScript in your browser to complete this form.

Instructions 

  • Preheat the oven to 400ºF. Take the broccoli out of the freezer and allow it to thaw as the potatoes bake. Once thawed, roughly chop the broccoli into small pieces and then set aside until ready to use.
  • Wash the potatoes well, then dry with paper towel or a clean dish towel. Use a fork to prick several holes in the skin of each potato. Pour the olive oil into a small dish, then use your hands to coat each potato in oil. Place the oil coated potatoes on a baking sheet, and season with a pinch of salt. Bake the potatoes for about 60 minutes, or until tender all the way through.
  • When there is about 15 minutes left in the baking time for the potatoes, begin to prepare the cheese sauce. Add the butter and flour to a medium sauce pot. Place the pot over a medium flame and whisk the butter and flour together as they melt. Allow the mixture to begin to bubble and foam, whisking continuously. Continue to cook for 2 minutes more to remove the raw flour flavor, but do not let the flour begin to brown.
  • Whisk the milk into the butter and flour mixture. Bring the milk up to a simmer, whisking frequently. When it reaches a simmer, it will thicken. Once thick enough to coat a spoon, turn off the heat. Season the white sauce with the salt and garlic powder.
  • Begin to whisk the shredded cheddar into the sauce one handful at a time, making sure the cheese is fully melted into the sauce before adding the next handful. Once all of the cheddar has been melted into the sauce, stir in the chopped broccoli.
  • When the potatoes are finished baking, carefully slice them open. Use a fork to slightly mash the insides of the potatoes. When ready to serve, place each potato on a plate or in a bowl and ladle the broccoli cheese sauce over each potato. Serve warm.

See how we calculate recipe costs here.


Nutrition

Serving: 1potatoCalories: 602.58kcalCarbohydrates: 56.2gProtein: 23.35gFat: 32.8gSodium: 1123.25mgFiber: 5.1g
Read our full nutrition disclaimer here.
Have you tried this recipe?Mention @budgetbytes or tag #budgetbytes on Instagram!

Scroll down for the step by step photos!

Overhead view of a broccoli cheddar stuffed potato in an individual white ceramic casserole dish

How to Make Baked Potatoes with Broccoli Cheese Sauce – Step by Step Photos

Prep russet potatoes for baking

Preheat the oven to 400ºF. Wash then dry four russet potatoes (about ¾ lb. each). Use a fork to prick the skin of the potatoes several times on each potato. Place 1 Tbsp olive oil in a dish, then use your hands to coat each potato in oil. Place the potatoes on a baking sheet or in a baking dish (with plenty of room around each potato), then season each potato with a pinch of salt. Place the potatoes in the preheated oven and bake for about one hour, or until they’re tender all the way through.

Thaw and chop frozen broccoli

While the potatoes are baking, thaw and chop ½ lb. of frozen broccoli into small pieces.

Shred Cheddar Cheese

Shred 6 oz. cheddar cheese.

Butter and flour in sauce pot for cheese sauce

When there is about 15 minutes left in the bake time for the potatoes, begin the cheese sauce. Add 3 Tbsp butter and 3 Tbsp butter to a sauce pot. Heat and whisk over medium heat, allowing the butter to melt and form a paste with the flour. When the paste begins to bubble up and sizzle, continue whisking and cooking for about 2 minutes to slightly toast the flour.

Whisk milk into flour and butter

Whisk 3 cups milk into the flour and butter mixture. Continue to cook and whisk until the milk reaches a gentle simmer.

Thickened milk coating the back of a spoon

When the milk reaches a simmer, the starch molecules from the flour will swell and thicken the sauce. When it’s thick enough to coat the back of a spoon, turn off the heat. Season the white sauce with ¼ tsp garlic powder and 1 tsp salt.

Whisk cheddar into white sauce

Begin whisking in the shredded cheddar, one handful at a time, allowing the residual heat of the sauce to fully melt the cheese before adding the next handful.

A whisk stirring the thickened cheese sauce

Once all the cheese is melted in, the sauce will be considerably thicker.

Stir chopped broccoli into cheese sauce

Stir the thawed and chopped broccoli into the cheese sauce.

Opened baked potatoes in the casserole dish

Once the potatoes are baked and tender all the way through (use a fork or a small knife to pierce the center to test the doneness), slice each potato lengthwise, then pinch each end and push in toward the center to open the potatoes. Use a fork to slightly mash the potato in its skin.

Broccoli cheese sauce being spooned onto baked potatoes

Spoon a generous amount of cheese sauce onto each baked potato. For best results, place each potato in its own serving dish before topping with broccoli cheese sauce, so any runoff will stay in the dish and can be eaten with the potato.

Side view of a baked potato with broccoli cheese sauce

Dig in!! Or check your fridge for any other toppings that you might want to pile on!

Share this recipe

Posted in: , , , , , , , ,

Leave a Comment

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.

Comments

Leave a Comment
  1. This is missing any instructions to cook the broccoli. Also, I cut down the milk quantity as it didn’t thicken as it should have.

    1. You don’t have to cook the broccoli! Frozen broccoli is already par-cooked so all you’d need to do is follow the thawing step. :)

    1. Yes! Just chop and pop the florets into a microwave safe bowl with a few tablespoons of water. Microwave until tender, about 3 to 4 minutes. XOXO -Monti

  2. Normally, my family complains if a meal doesn’t include meat. Still, I persist in an attempt to make them a tad healthier. But, oddly enough, no one brings up the lack of meat when I make this recipe. ;) I think that speaks for itself!

  3. Delicious but either I didn’t cook the bechamel enough or there is like, 2-3x the amount of sauce needed for the potatoes. Not upset because cheese sauce is good on everything, but keeping the brocolli the same, I think you could half the cheese sauce easy if you’re low on supplies. Either way, delicious and will def make again since it’s a good simple recipe.

  4. I used unsweetened macadamia nut milk and it turned out great.  I had blanched broccoli & asparagus I needed to use up. Served this over brown rice for a yummy lunch. Oh, and the hot sauce was a nice addition!

  5. I made this recipe exactly as listed and it was delicious! Will add some hot sauce to the leftovers tomorrow

        1. I’m not sure, I’ve never tried to make a cheese sauce with coconut milk. There’s definitely a bit of chemistry at work to get the cheese to emulsify, so I’m not sure if coconut milk will have quite the right make up for that. :)

      1. I just made this with almond milk last night and though it wasn’t as thick as I’m sure it would be with whole milk, it was very tasty! It turned out great for me. I didn’t have to use as much almond milk though, so a cup or more less than the recipe calls for. Coconut milk would probably be even better too!

  6. I halved the cheese sauce and still had a lot (about half a cup per potato). I served it as a side with the ham & bean soup.Â