Umberto Eco
This brilliant book by Italian intellectual, Umberto Eco, practically demonstrates how legends were created and myths were woven to attest to the divine origin of the King in the medieval times. Countless battles that serve no end, the ruin and re-birth of city-states in Italy, changing loyalties, mythical creatures in no man's land; all form a part of the canvas here. The king is Frederick Barbarossa (AOE enthusiasts might find the name familiar), and the protagonist, Baudolino, is his adopted son. Barbarossa is quick to spot Baudolino's savvy in lying and inventing tales for the gullible masses. We find that every time Baudolino tries to do something true and simple, fate plays out against him. He even "discovers" and soon loses the Holy Grail. The final search is for the Kingdom of Prester John, a story fabricated by the liar himself. What he finds there though, is beyond imagination. Eunuchs seem to rule a Kingdom of strange creatures (who have strong theological differences!) and Baudolino falls in love.
The geography and politics of medieval Europe are discussed in detail. The conflict between the Pope and the Patriarch of the Byzantine church figures prominently. Anti-popes abound! Constantinople is in a state of turmoil as the novel begins and Baudolino narrates the story of his life to Niketas, a historian.