I wasn’t able to find this novel since I've read it as a child/teenager at least 10 years ago, but more like 15.
The story goes somewhat like this:
A boy escapes the siege of his father’s castle. His family gets killed and he decides to travel as far away as he can. He meets a band of thieves and joins them. In their travel he somehow learns he is the Incarnation of a master swordsman and his quest is to find a girl which is also the Inkarnation of His Love. Somehow he find's her at a big caravan. He learns that they together need to find and save their original Homeland.