Yes, you can! I like to air-fry my frozen Brussels sprouts, though you can bake them in a traditional convection oven from frozen as well.