Tolkien, Arthur, the traditional "once upon a time" fairy tales...
Though if you think all fantasy's still pseudo-Medieval Europe, I suggest hitting the bookstore and/or library; many people have branched out to other eras and cultures... including prehistory and the far future.
Someone mentioned Codex Alera - that was written on a bet by Jim Butcher to combine the concepts of Pokemon and the Lost Roman Legion.
The popular YA series Percy Jackson & the Olympians (and the follow-up series, Heroes of Olympus) by Rick Riordan draws off Greek mythology. Riordan also writes The Kane Chronicles, which use Egyptian mythos as a base.
For Africa, the first one I thought of was The Leopard's Daughter by Lee Killough - it's set in a mystical prehistoric Africa, when the Sahara was green and animal spirits still crossbred with humans. (The heroine's father was a leopard-man.)
Pre-Columbian America's been getting more love lately. Long ago, though, I read and (mostly) enjoyed Clare Bell's The Jaguar Princess, about an Aztec slaver girl unknowingly descended from jaguar gods.
I've heard of (but never read) WWII fantasies, as well. I've heard good things about Ian Tregillis's Milkweed books, where the Nazis have demons. And for WW1 dieselpunk/biopunk, Scott Westerfield wrote the imaginative Leviathan trilogy.
I've also seen plenty of Asian-inspired fantasies, as well as some Arabic, go through the library. Not to mention fantasies that seem to defy traditional categorization.
Fantasy gets around these days... you just have to look for it.