In the Middle Ages, the town switched hands between the Byzantine Empire, Bulgaria and Serbia, prior to Ottoman annexation in 1395.

[4] A Thracian settlement was founded at the place of the modern town in the 5th-4th centuries BC and was known for its asclepion, a shrine dedicated to medicine god Asclepius.

[5] In the reign of Hadrian, the people both of Pautalia and Serdica added Ulpia to the name of their town, probably in consequence of some benefit received from that emperor.

Stephanus of Byzantium has a district called Paetalia (Παιταλία), which he assigns to Thrace, probably a false reading.

A second, smaller fortress of area 2 hectares was built in the town in the 4th century (known by its later Ottoman name Hisarlaka).

Many Thracian and Roman objects are exhibited in the town's Regional History Museum, most notably an impressive numismatic collection.

[7] The town was mentioned under the Slavic name of Velbazhd (Велбъжд, meaning "camel")[8] in a 1019 charter by the Byzantine Emperor Basil II.

[13] The city was a sanjak centre initially in Rumelia governorate-general, after that in the Bitola and Niš vilayets (province).

The residents of Kyustendil took an active part in the Bulgarian National Revival and crafts and trade flourished.

In Antiquity, Pautalia was a bishopric in the Roman province of Dacia Mediterranea, suffragan to the Metropolitan Archdiocese of Sardica, in the sway of the Patriarchate of Constantinople.

Its only recorded residential bishop was During the brief Late Medieval period, when the Bulgarian Church entered in full communion with Rome (instead of Orthodox Constantinople), one of its three 'Uniate Catholic' (equivalent to modern Eastern Catholic) sees was Velebusdus, which was even raised to a Metropolitan Latin Archbishopric as Pope Innocent III sent its incumbent Athanasius the archiepiscopal pallium on 25 February 1204.

It has had the following incumbents, so far of the fitting Metropolitan (highest; perhaps some merely of intermediary Archiepiscopal) rank : The city is the center of light and manufacturing industry: logging, footwear, knitwear, ready-made clothes, toys, packaging, alcohol producers, bakery, printing and canning industries.

Kyustendil is a center of an agricultural area with centuries-old traditions in the field of fruit growing, which is why the town and its surroundings are known as the "Orchard Garden of Bulgaria".

Kyustendil is located at the foot of the Osogovo mountain, on both banks of the Banshtica River and is a well-known centre of balneology and fruit growing.

The second half of the summer and early autumn in the town are the sunniest of the year, and the cloud cover is mostly in the winter months.

Синови деспота Дејана заједнички су управљали пространом облашћу у источној Македонији, мада је исправе чешће потписивао старији, Јован Драгаш.

Као и његов отац, Јован Драгаш је носио знаке деспотског достојанства.