People often talk about looking at real historical magic, and I find that generally useless and especially when you're talking about Europe. Genuine historical magic is people groping towards science, and there's nothing less numinous than magic that works like science. Genuine superstitions are a lot more useful for fantasy.
But the thing I've found useful is thinking about different cultures' different perceptions of destiny.
The Celts had this concept of geas, the destined thing that was going to get you, and everyone had a different one and some of them were very weird and you might or might not know yours. If you know you're going to be killed by a green boar with no ears, then you know you're safe in battle -- but if you tell your best friend, then when you steal his wife he might go out there with a barrel of dye looking for a boar. It's an interesting worldview.
The Norse believes in wyrd. Wyrd is odd -- you start off with free will, but everything you do constrains everything you can do, so that in the end everything is absolutely inevitable. (Writing novels is like this. The first word can be anything, but the last word has all the weight of what has come before pressing down to make it what it has to be.)
Classical Greece has Moira -- moira is the line drawn around the possibilities of your fate. You can't overstep the line -- that's hubris and it'll get you. But you should try to fill in as much as you can of your potential within the line. Of course, you can't see the line...
Christianity has providence -- everything happening for the best, everything meant to happen.
I have not encountered any human cultures that don't have a belief in some kind of destiny. What I've found useful in writing fantasy is to look at these kinds of ideas and then put two of them up against each other and see what I get.