慕容超在被刘裕大军围攻的时候，曾向盟国后秦紧急求救。姚兴本已派出步骑兵前往洛阳，准备与那里的军队合兵一处攻打晋军。然而，他却在与新兴强敌夏国的交锋中失利，不得不把援军追回。
姚兴后期的状况，与其早期相比，称得上糟糕。他在柴壁失败后，意识到拓跋珪的强大，和他重新通好。可是，这一举动又把那个投在他手下、与拓跋珪有杀父深仇的铁弗人刘勃勃惹怒。刘勃勃宣布独立，脱离后秦的管辖。
姚兴才刚给自己减少了一个敌人，就又增加了一个敌人，真是“此恨绵绵无绝期”。
刘卫辰的势力被北魏消灭后，刘勃勃在河套地区几经辗转，逃出了拓跋氏的势力圈，投奔姚兴的部下高平公没弈于。刘勃勃这个人的长相，用《晋书》里的话说是“性辩慧，美风仪”，用现代流行语讲就是帅哥。没弈于很赏识他，不但把他收留下来做部将，还把自己的女儿嫁给了他。
姚兴见到刘勃勃的第一反应，就认准了他是济世之才，立刻拜他做骁骑将军，还常常让他参与军国大事的讨论，对他宠爱有加。姚兴的弟弟姚邕看出些问题，对姚兴说：“刘勃勃这个人天性不仁，不能过于亲近。可是陛下对他的宠爱太过，实在让我不可思议。”
姚兴摇摇头说：“勃勃这样的济世之才，我正要与他共同平定天下，有什么不对的么？”
姚兴预备把刘勃勃升做安远将军，让他协助没弈于镇守边境地区的高平（今宁夏固原一带），并统领刘卫辰的旧部，待机伐魏。姚邕再三劝谏，认为绝不能这样做。
姚兴问他：“你怎么就知道勃勃的性情和为人？”
姚邕答道：“勃勃对上级傲慢无礼，对部下凶狠残忍，而且贪婪残暴，举止轻浮。对这样的人要是如此宠爱下去，早晚要成为边境的祸患。”
姚兴听了话，才有些犹豫，取消了对勃勃的任命。然而不久，姚兴还是把姚邕的劝谏彻底忘记，他任命刘勃勃为安北将军，交给他二万多鲜卑和杂胡部众，镇守朔方（今内蒙古杭锦旗北）。
所以当姚兴在后秦弘始九年（公元407年）与北魏正式交换战俘，达成友好协议时，刘勃勃已拥有足够的力量叛秦自立。恰好又在这时，北方新兴的柔然国的可汗向姚兴献马，途经朔方，刘勃勃就把这批战马全部留为己有，扩充军备。他对自己的老岳丈也绝不手软，召集三万多人的部众袭杀了没弈于，兼并了他的士卒，顿时壮大了自己的队伍。
刘勃勃认为匈奴是夏后氏（也就是夏朝君主）的后裔，就在这一年六月自称大夏天王、大单于，改元龙升，设置文武百官，建立了十六国中的最后一个国家——大夏。
高云建立的北燕则基本与夏国同时，因为在前面已经提到过，所以我在这里把夏国当作最后一个国家。刘勃勃的想法很怪，关于匈奴的起源，大致认为是春秋时期北方的几个狄族演化而成，更远的始祖还真不好追溯。刘渊当年认汉朝皇帝做祖宗，至少还是明摆着可算半对的，刘勃勃却认了个夏朝君主做祖宗，若真有些根据，可算得上对考古学有所贡献。夏朝的后代，按司马迁所说，封在杞国（就是我们常说的“杞人忧天”的杞），国灭后族人散居中原各地，何时又跑到北方去做匈奴，不可考。或者，就把这个问题，留作将来历史系某位研究生的学位论文题目吧，一定会很有意思。
刘勃勃以他收罗的那些军队，先攻破了鲜卑族的三个部落，收降一万多人。接着又进攻后秦三城（今山西代县西南）以北各据点，斩杀了杨丕、姚石生等后秦将领。
刘勃勃四处攻战，令部将十分不解，他们说：“陛下要想经营关中，就应该先巩固根据地，让人心倚向你。高平山川险固，土地肥沃，可以在那里定都。”
刘勃勃笑道：“你们呀，只知其一，不知其二。我刚刚白手起家，手下的人不多。姚兴也算是一时的英雄，关中现在还拿不下来。如果我专守一城，姚兴必然全力来攻，众寡不敌，失败就不远了。不如以铁骑与他周旋，出其不意，他如救前，我就击后，他如救后，我就击前，把他搞得疲于奔命，而我可以从从容容地夺他的粮草。不出十年，岭（秦岭）北、河东一带就全归我所有了。等到姚兴死后，他的儿子继立，那时就可夺取长安，至于策略，我已了然心中。”
刘勃勃的这一席见解，的确比当时很多政权，比如诸凉的君主要高明得多。后者往往只是停留在眼前利益上，据守一城一地，然后认准了目标攻杀，等到旁边出现一个稍稍强大些的政权，就维持不了太久。刘勃勃有组织有目的地打游击战，颇像当年姚苌对付苻登的那一套。姚兴被他父亲曾经使用过的招数，拖得几乎绝望。
当刘勃勃率军大掠岭北时，岭北各城吓得连白天都不敢打开城门。姚兴不禁大发感慨：“悔不听我兄弟的话，竟弄到现在这样的地步！”
夏国的西面，是当时已经占据了后凉旧都姑臧的南凉。
这时候的南凉是第三代君主秃发傉檀在位。此人在即位之前被一致看好，所以南凉的君主都是传弟不传子，就是要让他上台“光宗耀祖”。他的所作所为却让人难以看出这种迹象，他与僻处西北的北凉王沮渠蒙逊连年打架，已经属于很没出息，却还要带兵攻打附近一堆不入流的小部落，国势被他消耗得差不多。刘勃勃向他要求联姻，遭到拒绝，生了气，亲率两万骑兵攻打南凉，杀伤掳掠的南凉军民不下数万，牛羊更是不计其数。
秃发傉檀也是个吃软不吃硬的，他不听部下劝告，在刘勃勃撤退时领兵紧追不舍。刘勃勃用战车堵了退路，率军迎击秃发傉檀。
秃发傉檀不想着如何迎战，倒知道找个神箭手去射刘勃勃，然而这箭只射中他的左臂，而没能射掉他的斗志。夏军大获全胜，一口气追击八十余里，又杀伤了数万南凉士卒。刘勃勃对自己的战利很欣赏，下令把死尸堆积成一座高台，取名叫做“骷髅台”。
刘勃勃此后又连连击败后秦的军队，篇首所说的那次战役是姚兴的御驾亲征。姚兴不仅没捞到半点便宜，还损兵折将，丢了不少城池。
刘勃勃在得意之余想到给自己改姓，他觉得祖辈随母姓刘的做法不合礼制，命本族人改姓赫连。赫连的意思，即帝王是上天之子，他的徽赫与天相连。而非正统的族人，则以铁伐为姓氏，表示刚锐如铁，足以用来攻伐。
他在凤翔元年（公元413年），征发岭北的胡汉各族在朔方一带修筑新城，取名统万，以表达他统一天下，君临万邦的决心。
他所派去监工的大臣叱干阿利比他更残忍，他在筑城时，用利器检查城墙的质量，只要利器能刺入一寸，就把造这堵墙的人杀掉，将尸体一并筑入城墙。
赫连勃勃对这样的筑城方案大加赞赏，接着让他监造兵器，制造出来的兵器同样要经过杀人验收：弓箭射不穿盔甲，造弓箭的工匠就被杀；弓箭射穿盔甲，造盔甲的工匠就活不成。一件件精致锐利的兵器就在这样的死亡游戏中制造出来。
赫连勃勃作为末代匈奴，以这种方式把匈奴人的凶残发挥到了极致。他在公元五世纪初的一系列“表演”，也就成为匈奴人在东方这块舞台上的绝唱。