赫连最初僭号时，向南凉君主秃发傉檀请求娶他的女儿为妻，秃发傉檀没有答应。赫连很生气，率领二万骑兵攻打秃发傉檀，从杨非打到支共三百多里，杀伤一万多人，抢掠二万七千人和数十万羊回来。秃发傉檀率领军队追赶，将领焦朗对秃发傉檀说：“赫连天豪雄，治理军队严厉整肃，不能轻视。现在他凭着抢掠到的资财，率领着盼望归去的战士，人自为战，难以和他争胜。不如从温围向北渡河，到万斛堆，凭借河建造营寨，扼制住咽要地，这是百战百胜的办法。”

赫连和后秦将领张佛生在青石原战，打败张佛生，俘获和杀死五千七百人。姚兴派将领齐难率领二万军队来攻打赫连，赫连退到河曲。姚兴因为离赫连已经很远，就放纵士兵四抢掠，赫连秘密地派兵伏击齐难，俘获七千多人，收缴他们的战兵。齐难领兵后退，赫连又追击到木城，攻克木城，擒获齐难，俘获一万三千人，一万匹战。岭北的夷人、汉人向赫连投降归附的有数万，赫连设守宰来安抚他们。赫连又率领二万骑兵冈，到达五井，抢掠七千多平凉的杂胡分派到后军里，驻依力川。

连便筑堤坝截断，敕奇堡里的人们很窘迫，把王奚抓起来投降。赫连对王奚说：“你是个忠臣！朕正要和你一起平定天下。”王奚说：“如能蒙受大恩，让我早死，这就是恩德。”于是和亲近的数十人一起自杀而死。赫连又到黄石固攻打姚兴的将领金洛生，到我罗城攻打弥豪地，都攻克，把七千多迁徙到大城，任命其兄丞相赫连右地代领幽州牧来镇守。

秃发傉檀的将领贺连愤怒地说：“赫连用残余之力，率领乌合之众，反叛作，构成祸患，侥幸有了大功绩。现在他羊多得堵路，财宝多得像山一样，窘迫疲敝之余，人人怀着贪求之心，赫连再也不能督率策励士兵来抵抗我们。我们用大军去攻打他们，他们一定会彻底崩溃。现在率领军队避开他们，是向敌人显示怯弱。我们的军队气势正盛，应该迅速追击。”秃发傉檀说：“我追击之计已定，敢劝谏的人杀死！”赫连听到消息后非常兴，就在武下狭凿开冰凌埋车来堵路。秃发傉檀派善于箭的士兵他们，中赫连的左臂。赫连率领军队迎战，把秃发傉檀打得大败，追赶八十多里，死伤数以万计，杀死南凉十多员大将，把尸首堆成了封土的台，取名为“髑髅台”，返回岭北。

姚兴前来攻打，到达三城，赫连趁着姚兴各路军队还没有会合，率领骑兵攻打他们。姚兴非常害怕，派他的将领姚文宗迎战，赫连假装后退，设下埋伏等候。姚兴派他的将领姚榆生等率兵追击，赫连的伏兵夹击，把他们全都俘获。姚兴的将领王奚在敕奇堡聚集三千多羌人，赫连攻王奚。王奚骁勇有力，短兵相接时，赫连的士兵有很多受伤。

赫连派尚书金纂率领一万骑兵攻打平凉，姚兴赶来救援，金纂被姚兴打败，战死。赫连哥哥的儿左将军赫连罗提率领一万步兵、骑兵到定攻打姚兴的将领姚广都，攻克后坑杀四千多人，把妇女作为军中的奖赏。任命姚广都为太常。赫连又到清城攻打姚兴的将领姚寿都，姚寿都逃到上

定会合力对付我们，我们的军队不是他们的对手，很快就会灭亡。我们风云般急速前去，其不意，他们救援前军我们就攻打后军，救援后军就攻打前军，使他们疲于奔命，我们则从容自若，不十年，岭北、河东就会全归我所有。等到姚兴死后，再逐步地攻取长安。姚兴的儿姚泓是个平庸懦弱小儿，擒获他的计谋策略，已经在我的算计之中。从前轩辕氏也曾经有二十多年迁居无常，难单是我一个人吗！”于是侵犯掠夺后秦岭北地区，岭北的各个城门白天不敢打开。姚兴叹说：“我不采用姚邕的话，以致到如此地步！”