回纥，其先匈奴之裔也，在后魏时，号铁勒部落。其众微小，其俗骁强，依托高车，臣属突厥，近谓之特勒。无君长，居无恒所，随水草流移，人性凶忍，善骑射，贪婪尤甚，以寇抄为生。自突厥有国，东西征讨，皆资其用，以制北荒。
隋开皇末，晋王广北征突厥，大破步迦可汗，特勒于是分散。大业元年，突厥处罗可汗击特勒诸部，厚敛其物，又猜忌薛延陀，恐为变，遂集其渠帅数百人尽诛之，特勒由是叛。特勒始有仆骨、同罗、回纥、拔野古、覆罗，并号俟斤，后称回纥焉。在薛延陀北境，居娑陵水侧，去长安六千九百里。随逐水草，胜兵五万，人口十万人。
初，有特健俟斤死，有子曰菩萨，部落以为贤而立之。贞观初，菩萨与薛延陀侵突厥北边，突厥颉利可汗遣子欲谷设率十万骑讨之，菩萨领骑五千与战，破之于马鬛山。因逐北至于天山，又进击，大破之，俘其部众，回纥由是大振。因率其众附于薛延陀，号菩萨为“活颉利发”，仍遣使朝贡。
菩萨劲勇，有胆气，善筹策，每对敌临阵，必身先士卒，以少制众，常以战阵射猎为务。其母乌罗浑，主知争讼之事，平反严明，部内齐肃。回纥之盛，由菩萨之兴焉。
贞观中擒降突厥颉利等可汗之后，北虏唯菩萨、薛延陀为盛。太宗册北突厥莫贺咄为可汗，遣统回纥、仆骨、同罗、思结、阿跌等部，回纥酋帅吐迷度与诸部大破薛延陀多弥可汗，遂并其部曲，奄有其地。
贞观二十年，南过贺兰山，临黄河，遣使入贡，以破薛延陀功，赐宴内殿。
太宗幸灵武，受其降款，因请回鹘已南置邮递，通管北方。太宗为置六府七州，府置都督，州置刺史，府州皆置长史、司马已下官主之。以回纥部为瀚海府，拜其俟利发吐迷度为怀化大将军兼瀚海都督。时吐迷度已自称可汗，署官号皆如突厥故事。以多览为燕然府，仆骨为金徽府，拔野古为幽陵府，同罗为龟林府，思结为卢山府，浑都为皋兰州，斛萨为高阙州，阿跌为鸡田州，契苾为榆溪州，跌结为鸡鹿州，阿布思为蹛林州，白霫为寘颜州；又以回纥西北结骨为坚昆府，其北骨利干为玄阙州，东北俱罗勃为烛龙州。于故单于台置燕然都护府统之，以导宾贡。
贞观二十二年，吐迷度为其侄乌纥所杀。初，乌纥蒸其叔母，遂与俱陆莫贺达干俱罗勃潜谋杀吐迷度以归车鼻。乌纥、俱罗勃，并车鼻之婿也，乌纥遂夜领骑十余劫吐迷度，杀之。燕然副都护元礼臣遣人绐乌纥云：“将奏而为都督，替吐迷度也。”乌纥轻骑至礼臣所，跪拜致谢，礼臣擒而斩之以闻。
太宗恐回纥部落携离，十月，遣兵部尚书崔敦礼往安抚之，仍以敦礼为金山道副将军。赠吐迷度左卫大将军，赙物及衣服设祭甚厚。以吐迷度子前左屯卫大将军、翊卫左郎将婆闰为左骁卫大将军、大俟利发、使持节回纥部落诸军事、瀚海都督。后俱罗勃来朝，太宗留之不遣。诏西突厥可汗阿史那贺鲁统五啜、五俟斤二十余部，居多罗斯水南，去西州马行十五日程。回纥不肯西属突厥。
永徽二年，贺鲁破北庭，诏将军梁建方、契苾何力领兵二万，取回纥五万骑，大破贺鲁，收复北庭。显庆元年，贺鲁又犯边。诏程知节、苏定方、任雅相、萧嗣业领兵并回纥大破贺鲁于阴山，再破于金牙山，尽收所据之地，西遂至耶罗川。
贺鲁西奔石国，婆闰随苏定方逐贺鲁至石国西北苏咄城，城主伊达干执贺鲁送洛阳。以其地置濛池、昆陵府，以阿史那弥射、阿史那步真为二府都督，统十姓右厢五弩失毕、左厢五咄陆。以贺鲁种落分置州县，西尽波斯。加婆闰右卫大将军兼瀚海都督。
永徽六年，回鹘遣兵随萧嗣业讨高丽。龙朔中，婆闰死，侄比粟毒主领回鹘，与同罗、仆固犯边，高宗命郑仁泰讨平仆固等，比粟毒败走，因以铁勒本部为天山县。永隆中独解支，嗣圣中伏帝匐。开元中承宗、伏帝难，并继为酋长，皆受都督号以统蕃州，左杀右杀分管诸部。