According to some sources the Kremenets fortress was built in the 8th or 9th century, and later became a part of Kievan Rus'. The first documented reference to the fortress is given in a Polish encyclopedic dictionary written in 1064. The first reference to Kremenets in Old Slavic literature dates from 1226 when the city's ruler, Mstislav the Bold, defeated the Hungarian army of King Andrew II nearby. During the Mongol invasion of Rus in 1240–1241, Kremenets was one of few cities that Batu Khan failed to capture. In 1382, after the death of Louis I of Hungary, Lithuanian duke Liubartas captured Kremenets from the Kingdom of Hungary. The city obtained Magdeburg rights in 1431, and in 1569, after the Union of Lublin, it became part of Crown of Poland, known as .