Go with mythology. You'll take away the most work you have to put into a fantasy story, namely building a believable world that can stand on its own. Also by reading some epics you'll be bound to be inspired by something.
If you don't want to here's a prompt. In high-medieval Europe you're a Romani, so a gypsy. You're a nobody and have to move with the caravan often, but you like your life. However on one day you find yourselves in the middle of a war between two German dukes.
Then, while scavenging one battlefield you're the first to spot a full plate armour. The curious bloke you are, you try to put it on. As you then proceed to bask in your own glory, you're captured by a battalion of mounted knights. They take you prisoner and intend to ransom you. Damn tough luck, you'll have to convince them that you're the real deal in order to stay alive.
You can then proceed to put in dragons and other medieval fantasies from that time period into this world. Props if you can combine fantasy and history into a story that would fit both believably.