唐贞观二十二年（648年），铁勒结骨（黠戛斯、Yenisei Kirgiz）部族内附，唐设坚昆都督府，以其首领失钵屈阿栈为都督，隶燕然都护府。663年转隶属于瀚海都护府，669年隶属于安北大都护府。693年，安北大都护府由漠北迁至漠南，坚昆都督府才终结建制，前后存在45年。唐乾元年间（759年）为回鹘所征服。故治在今俄罗斯叶尼塞河上游一带。

唐代，坚昆被称为“黠戛斯”。当时，他们在政治上十分活跃，和唐朝建立了密切的联系。贞观二十二年（648），黠戛斯首领俟利发失钵屈阿栈亲自到唐朝朝贡。唐太宗隆重设宴招待。在宴席上，俟利发失钵屈阿栈向唐太宗表达了做唐朝臣子的愿望：“臣既一心归国，望得国家官职，持笏而已。”唐太宗就在黠戛斯生活之地设立坚昆都督府，授予俟利发失钵屈阿栈左屯卫大将军，任都督，隶属燕然都护。此后，唐高宗时，黠戛斯两次派遣使者前往唐都长安。景龙二年（708），黠戛斯使者又前往长安贡献地方特产，受到唐中宗的热情款待。

开元六年（718），唐朝派30万大军征讨后突厥，坚昆都督右武卫大将军骨笃禄毗伽可汗及其部众也参加了这次战争。在这次战争中，黠戛斯兵众英勇善战，受到唐玄宗的夸奖，称赞其军队“弧矢之利，所向无前”。在此前后，后突厥与唐朝关系趋于缓和，交往增多，这种气氛对于黠戛斯与唐朝友好关系的发展十分有利。开元十年（722），坚昆大首领伊悉钵舍友者毕施颉斤与后突厥大首领一起前往唐朝，唐朝分别授予其中郎将、将军之号。第二年，坚昆大首领俱力贫贺忠颉斤与后突厥大首领一起前往唐朝，唐朝又分别授予其郎将、将军之号。第三年，坚昆又遣使前往唐朝贡献良马。

7世纪中叶，回鹘人推翻了突厥在蒙古高原的统治，建立了回鹘汗国，黠戛斯又处于回鹘的统治之下。840年，黠戛斯人趁回鹘汗国统治阶级内部发生政权内讧之际，联合其汗国内部的反对派，里应外合，一举推翻回鹘汗国，建立黠戛斯汗国，并恢复了与唐朝的联系与友好往来。