През V-ІV век пр.н.е. траките основават селище привлечени от лековитите минерални извори и плодородната земя. През І век римляните превръщат града в балнеологичен курорт, важен административен, търговски и културен център.
В историята Кюстендил е известен с имената Пауталия, Улпия Пауталия, Пауталия Аврелий, Велбъжд, Константинова баня, Ълъджа, Баня, Коласия, Кюстендил.
В писмените извори град Кюстендил е засвидетелстван за пръв път през 135 г. под името Пауталия. Градът бил здраво защитен с крепостните си стени, а стратегическото положение на Пауталия с хълмът над нея (днешният Хисарлък), позволявало на града да има и свое по-надеждно защитено място – свой акропол. Специфичните условия на Пауталия, породени от лековитите извори и благоприятния климат поставили на голяма висота почитането на здравеносният бог Асклепий. В негова чест бил изграден здравеносен център (Асклепион), който по размери се нарежда веднага след Епидавърския, най-големият в рамките на Римската империя.
Кюстендилския край е център на район с развита стопанска дейност още от древността. Добива се и се обработва желязо, олово, сребро, мед и злато. Добре развити са занаятите за производство на сечива, предмети за бита, ювелирни произведения, оръжие, облекло и хранителни продукти.
Едни от най – ранните известни селища и открити археологически материали в Кюстендилския край са от неолита (новокаменната епоха). Намират се край с. Шишковци, Невестино и Таваличево. Селища от енеолита (каменно – медната епоха) са открити край с. Невестино, Злогош, Таваличево, Неделкова Гращица, Пелатиково, Ваксево и Илия. От бронзовата епоха са локализирани само отделни находки при селата Таваличево, Невестино, Ваксево и в Кюстендил при разкопките на Килийното училище.Присъствието на траките в Кюстендилско датира от края на бронзовата епоха (втората половина на ІІ хилядолетие пр.н.е.). Известни са племената пеони, агриани, дентелети и др. От тях най-голямо е племето на дентелетите. По-късно името му приема и цялата област – Дентелетика. След падането на Тракия под римска власт (45 от н.е.) за дентелетите като за отделно племе вече не се говори. В отделни надписи се споменава принадлежността към тях на военнослужещи в римската войска. До римския период показва високо развитие на стопанския, политически и културен живот на тракийското население от района.
Пауталия наследява старото селище на дентелетите.
През римската епоха Пауталия е един от най-големите градски центрове в провинция Тракия. След 45 от н.е. земите на дентелетите са включени в стратегиите Полска Дентелетика (равнините по горното течение на р. Струма и долината на р. Джерман) и Планинска Дентелетика (пл. Осогово, Кюстендилско краище и Трънско), които през ІІ в. се обединяват с център Пауталия. По-късно големият градски център получава обширни територии, а стратегиите се премахват.
При император Марк Улпий Траян (98-117) Пауталия наред с други големи градове получава градски права и добавя към името си представка “Улпия”. От император Антонин Пий (138-161) до Каракала (198-217) градът сече свои бронзови монети. Пауталия е отбелязана на Певтингеровата карта като станция по пътя Сердика - Стоби.
Едно отклонение от този път, минаващо през Пауталия е за Тесалоника днешен Солун, а друго през Германия днешен град Сапарева баня – за Филипопол днешен Пловдив. При Пауталия е била и връзката за пътя Сердика – Наисус днешен Ниш. Античиният град е добре укрепен. Във времето от ІІ до ІV век укрепената площ е близо 30 хектара. В късната античност през ІV – VІ век Пауталия разполага с втора крепост, разположена на хълма Хисарлъка над града.
Добрите градоустройствени условия, икономическите предпоставки и непрекъснатата селищна традиция превръщат Пауталия в едно от най-цветущите селища за онова време. Върху серия монети, който били сечени при Юлия Домна и Каракала, е изобразена персонификация на града – млада жена, заобиколена от четири гения, които символизират главните богатства на този край: Жито, грозде, злато и сребро. Според историците в града е имало стадион за спортни състезания, храмове и светилища.
Територията на антична Пауталия е обявена за археологически резерват. Не се знае със сигурност територията, която е владеел градът, но се предполага се, че тя е обхващала цялата Дентелетика и част от Медика. Пауталия се споменава в произведенията на античните автори Малх, Комес Марцелин, Хиерокъл, Прокопи Кесарийски и Стефан Византийски. За последен път името на града е спомената през 553 г., след което се говори вече за Велбъжд.
По време на Първата българска държава градът и неговите околности попадат в заетите от славяните обширни области. В писмени източници името на града се среща като Велесвуздуион, Велевузда, Велевуздиум, Велесвуздиум, Велбужд, Велбужка баня и Велбондж. Градът е присъединен към новосъздадената Българска държава по времето на хан Крум около 809 година. След въвеждането в България на християнството като официална религия през 864 година при цар Борис I, Велбъжд става важен епископски център.
Продължена е селищната традиция от античността.
При разкопките при сегашната сграда на художествената галерия "Владимир Димитров - Майстора" са разкрити вкопани и наземни жилища. Българите възстановяват крепостната стена и я използват. След завладяването на североизточна България от Византия през 971 година, Велбъжд остава в територията на Самуиловата държава. В близост до града се намирали родовите имения на комитопулите. По време на византийското иго в Кюстендилския регион се разпространяват павликяснството и богомилството. Свиделство за това са запазените и до днес имена на села като Котугерци, Еремия, Богослов, Недокръщеница.
Около Велбъжд израстват големи манастирски комплекси, свързани с живота на и дейността на български светци като Иван Рилски, Йоаким Осоговски, Прохор Прински, Йоан Девичи. По време на византийската власт значението на Велбъжд нараства и в грамота на император Алексий I Комнин той е споменат на трето място преди Средец. След отхвърляне на византийската власт - Велбъжд отново е български град.
Икономическият живот на града в свързан предимно с експлоатацията на рудни залежи и обработката на метали. Привлечени на работа са опитни рудари от Средна и Западна Европа. Добре развити са керамичното производство и традиционните земеделие и скотовъдство. Активно са използвани топлите минерални извори. По време на управлението на Деяновци е образувано Велбъждското княжество с център Велбъжд. Той е последният голям български град загубил независимостта си. Последен владетел на Кюстендил е Юсуф.
Историята на Кюстендил през първите години на османското иго не са осветени добре от писмени извори.
Участието на Юсуф във войната за трона между синовете на Баязид, на страната на Мохамед срещу Муса, осигурява на княжеството спокойно същестуване след победата на Мохамед. Това продължава вероятно до края на живота на Юсуф. През третото десетилетие на XV век вероятно през 1427 ли 1428 година, българите въстават срещу османската власт. Османските войски, предвождани от бейлербея на Румелия Турхан паша, превземат града и сриват крепостните стени. Кюстендил става един от най-богатите санджаци в Румелия. В него влизат някогашните Константинови земи. Обхващал Радомир, Дупница, Петрич, Мелник, Дойран, Тиквеш, Велес, Радовиш, Щип, Кратово, Враня, а по-късно и Паланка. По това време изчезва и името Велбъжд. Градът е наречен Коласия, Баня, Константинова баня.
По време на османското владичество градът запазва митрополитическия си престол. Посредством много пратиничества митрополията е поддържала тесни връзки с Русия и Руската църква, която е оказвала материална помощ за възстановяването на манастири и църкви, снабдявала е с книги и материали, дарявала е пари. Българското население в Кюстендилския край не се примирява с робската действителност и при всеки удобен случай прави опит да се освободи. Появяват се хайдушки дружини, населението се готви да посрещне и и подпомогне австрийските войски, достигали до Кюстендил неколкократно по време на войните срещу Османската империя. На два пъти през 1690 и 1737 година населението на града вижда европейски войски. Радостта била краткотрайна, а надеждите напразни.
Възраждането преобразява преди всичко духовния облик на българското население в Кюстендилския край.
В празниците, ритуалите, в народното творчество и бита се запазват и доразвиват етническите ценности. Остават чисти езикът и начинът на живот с минимални заемки и влияния. Издига се националното самосъзнание , разширява се участието на българите в търговията, поддържат се връзки с редица градове в страната и Западна Европа, Северна Африка и Близкият изток. Образуват се занаятчийски сдружения - еснафи с първомайстори, чираци и калфи българи. Манастирите изграждат свои метоси и все повече изпращат свои представители в градовете и селата. Строят се редица църкви в града. Засилва се и придобива остър характер борбата срещу Цариградската патриаршия. Върховната и точка е изгонването на гръцките митрополити Игнатий и Дионисий .
Нуждата от образование и духовно издигане довежда до откриването на първото училище в града през 1820 год. Освен това по-заможните изпращат децата си да учат в чужбина. Израства млада демократично настроена интелигенция. През 1869 година се създава първото читалище в града. Гради се нова възрожденска архитектура. През възраждането Кюстендил се оформя като един от центровете, изиграли значителна роля в националноосвободителните борби в Югозападна България. С легендарна слава се ползват Ильо Войвода и Румена Войвода. Хайдутството преминава в революционна борба за национално освобождение.
По стечение на обстоятелствата Кюстендил е последният град паднал под османско владичество и последният град освободен благодарение на навременната намеса на Ильо Войвода, на въстаническите сили на С. Соколов, с решаващата помощ на братята освободители и съдействието на софийския вицегубернатор професор Марин Дринов и италианския консул Виторио Позитано.
На 30 Януари 1878 година градът е освободен. За пръв комендант е назначен подпоручик Н. Савойски. Освободителите помагат на жителите на града да сформират временно градско управление, съдействат им във всички области за уреждане на основните институции на новоосвободения град. Всяка година в Кюстендил тържествено се отбелязва освобождението на града от Осмаснко робство.