There is evidence of prehistoric settlements in
many areas of the Czech Republic. The area where Prague is today is thought
to have served as an important crossroads for trading as early as Paleolithic
times. The area was intermittently populated by Celtic and Germanic tribes
until around the end of the fifth century when it was settled by Slavic
tribes. There are legends accompanying the founding of Prague, especially
that of Princess Libuse and her plowman husband, Premysl. Premysl and Libuse
founded Bohemia's First Dynasty known as the Przemyslid dynasty.

During the reign of the Przemyslid dynasty, the Czech state became stronger
and maintained its sovereignty. During the ninth century, a wooden fortress
was built in the district known today as Vysehrad on the east bank of the
Vltava river and then another wooden fortress was built on the Hradcany
heights on the western bank of the river. In the next few centuries, these
wooden fortresses were replaced with stone. Across the river from the Hradcany
fortress, which is usually known as the castle, an area called Staré
Mesto, or Old Town, was built. In the latter half of the thirteenth century,
Malá Strana, or Lesser Quarter, was founded below the castle on the
west bank of the Vltava River.