At court and on the battlefield, he is educated in reading and writing Latin and learns about the power struggles and battles of northern Italy at the time.

In Paris, he gains friends (such as the Archpoet, Abdul, Robert de Boron and Kyot, the purported source of Wolfram von Eschenbach's Parzival) and learns about the legendary kingdom of Prester John.

The earlier parts of the story follow the general historical and geographical outlines of 12th-century Europe, with special emphasis on the Emperor Frederick's futile efforts to subdue the increasingly independent and assertive city states of Northern Italy.

During the siege, Baudolino works on the side of Frederick Barbarossa, but concocts a plan to help win the Alessandrian townspeople independence.

After the Emperor's death, Baudolino and his friends set off on a long journey, encompassing 15 years, to find the Kingdom of Prester John.

After many disastrous adventures, the destruction of Prester John's Kingdom by the White Huns followed by a long stint of slavery at the hands of the Old Man of the Mountain, Baudolino and surviving members of his band of friends return to Constantinople undergoing the agony of the Fourth Crusade – the book's starting point.