If you go through all the fate cards in the deck, what do you do.

I know you reshuffle them in fall, but if the deck is empy before then, what do you do?

Well, OFFICIALLY what are you supposed to do?

Predator said:

You shuffle them anytime you need to draw one and there aren't any left. See the "Resolving Fate Cards" box on page 27 (the third bullet point).