Kyustendil (Bulgarian: Кюстендил [kʲustenˈdiɫ]) is a town in the far west of Bulgaria, the capital of the Kyustendil Province, a former bishopric and present Latin Catholic titular see.

The town is situated in the southern part of the Kyustendil Valley, near the borders of Serbia and North Macedonia; 90 km southwest of Sofia, 130 km northeast of Skopje and 243 km north of Thessaloniki. The population is 37 799, with a Bulgarian majority and a Roma minority. During the Iron Age, a Thracian settlement was located within the town, later known as Roman in the 1st century AD. In the Middle Ages, the town switched hands between the Byzantine Empire, Bulgaria and Serbia, prior to Ottoman annexation in 1395. After centuries of Ottoman rule, the town became part of an independent Bulgarian state in 1878.

The modern name is derived from Kösten, the Turkified name of the 14th-century Serbian magnate Constantine Dragaš, from Latin constans, "steadfast" + the Turkish il "shire, county" or "bath/spa". The town was known as Pautalia (Greek: Παυταλία) in Antiquity and as Velbazhd (Latin Velebusdus; Medieval Greek: Belebousda; Bulgarian: Велбъжд; Serbian: Велбужд) in the Middle Ages.

Kyustendil Ridge in Graham Land, Antarctica is named after the city, and Pautalia Glacier on Livingston Island in the South Shetland Islands, Antarctica is named after Pautalia (its Thracian ancestor settlement).

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.

Under the name Pautalia (Ancient Greek: Παυταλία or Πανταλία) it was a town in the district of Dentheletica. Its position in the Peutinger Table places Pautalia at Kyustendil; and the situation of this town at the sources of the Strymon agrees remarkably with the figure of a river-god, accompanied by the "legend" Στρύμων ("Strymon"), on some of the autonomous coins of Pautalia, as well as with the letters ΕΝ. ΠΑΙΩ. ("En. Paio"), which, on other coins, show that the inhabitants considered themselves to be Paeonians, like the other inhabitants of the banks of that river. On another coin of Pautalia, the productions of its territory are alluded to, namely, gold, silver, wine, and corn. 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.

In the 1st century AD, it was administratively part of Macedonia. Later the city was part of the province of Dacia Mediterranea and the third largest city in the province.

The Roman fortress of Pautalia of the 2nd to 4th century had an area of over 29 hectares (appr. 72 acres). The fortress wall was built mainly of granite blocks and unusually its façade was supported with pillars and arches behind. The wall was 2.5m wide allowing small catapults to be mounted atop.