The first mention refers to the XII century. The origin of the name according to a legend comes from a huge deer-stag which brought Yaroslav Osmomysl's wife out of the forest. She lost her way during the hunting. On the place where the princess had seen the deer, the prince ordered to build a tower. Around it was formed a town. In 1520 during one of the Tartars raids Nastya Lisovs'ka was captured. Nastya is known in history as Roksolana. She became a wife of sultan Suleyman.
In 1535 it was given the Magdeburg Right.
In 1415 city got own seal in the form of a horn with letter "R". In 1535 the city got an emblem in which letter "R" for some period of time (till 1557) was replaced to letter "B" to signify the name "Bona". It was the name of the wife of king Zhyhmont I.