成功稳住北边的突厥，又平定了宗室的政变，杨坚眼下最大的挑战就是尉迟迥，而尉迟迥的影响力确实不容小觑。
青州总管尉迟勤是尉迟迥的侄子，刚收到尉迟迥的信时，他派人把信送到长安，但没过多久还是和尉迟迥绑在了一起。
尉迟迥所统辖的相、卫、黎、洺、贝、赵、冀、瀛、沧等州，再加上尉迟勤所统辖的青、齐、胶、光、莒等州，军队多达数十万人。
除此之外，荥州刺史邵公宇文胄、申州刺史李惠、东楚州刺史费也利进和潼州刺史曹孝远等都各据本州，徐州总管司录席毗罗占据兖州，前东平郡守毕义绪占据兰陵，都起兵响应尉迟迥，怀县永桥镇将纥豆陵惠也向他投降。
尉迟迥派他所任命的大将军石逊攻打建州，建州刺史宇文弁献城投降。尉迟迥又派西道行台韩长业攻克潞州，生擒潞州刺史赵威，以郭子胜为刺史。
与此同时，纥豆陵惠攻陷巨鹿，接着又进围恒州。上大将军宇文威攻打汴州，莒州刺史乌丸尼等率领青、齐两州军队围攻沂州。大将军檀让攻克曹、亳二州后，驻军梁郡。席毗罗的军队有八万之众，驻兵蕃城，攻克了昌虑、下邑两座县城。李惠自申州进攻永州，攻克了永州城。
形势一片大好，尉迟迥又派使者招附大左辅、并州刺史李穆，李穆却将他所派来的使者抓了起来，连同书信一起送上朝廷。
李穆的儿子李士荣认为并州是天下精兵所聚之地，暗中劝说李穆响应尉迟迥，李穆坚决拒绝。杨坚派内史大夫柳裘到李穆处，向他陈说利害，又派李穆的儿子左侍上士李浑到并州，向李穆转达他以诚相待之意，极力拉拢。
于是，李穆派李浑送了一个熨斗给杨坚，对他道：”希望你能执掌威柄以安天下。”又送给杨坚十三环金带。十三环金带只有天子才能佩带，杨坚非常高兴，连忙派李浑到行军元帅韦孝宽那里，告诉他李穆的态度。
李穆的侄子李崇时任怀州刺史，一开始也想响应尉迟迥，得知李穆支持杨坚后慨然叹息道：“我全家得到富贵者多达数十人，现在国家有难，竟不能匡扶皇室，还有什么面目立于天地之间呢！”不得已之下也依附了杨坚。
李穆是宇文泰创业时的元老级人物，还曾救过宇文泰的性命，资历和威望无人能比，他的力挺对于杨坚来说至关重要。
尉迟迥的儿子尉迟谊时任朔州刺史，李穆派兵将其抓获，押送长安，又派军队讨伐郭子胜，也将其擒获，沉重打压了尉迟迥的气焰。
尉迟迥又想招附徐州总管源雄和东郡太守于仲文，二人都不肯顺从。
源雄是源贺的曾孙，于仲文是于谨的孙子，都是根深蒂固的门阀世家，他们的立场也从侧面反映了一个事实，北周实际上是门阀联合体，当宇文赟的暴虐将宇文氏的名声糟蹋得面目全非时，口碑更好的杨氏成为新一代盟主。
对于这些不利的信号，尉迟迥当然看得懂，但他别无选择，只能硬磕到底，派宇文胄由石济渡河，宇文威由白马渡河，分两路攻打于仲文，于仲文被迫放弃东郡，逃回长安，尉迟迥杀了他的妻儿。
接着，尉迟迥派檀让略地河南，杨坚以于仲文为河南道行军总管，派他到洛阳讨伐檀让，同时命杨素讨伐宇文胄。
就在这时，尉迟迥迎来了一个好消息，郧州总管司马消难举兵响应他。
公元580年七月二十六，杨坚以柱国王谊为行军元帅，率军讨伐司马消难。
于仲文的哥哥、广州刺史于顗（音同以）因与吴州总管赵文表不和，就假称得了心病引诱赵文表来探视，然后亲手杀了他，并宣称他与尉迟迥通谋。杨坚因尉迟迥尚未平定，只得睁一只眼闭一只眼，还以他为吴州总管。
与此同时，赵王宇文招又开始密谋除掉杨坚，邀请他来做客，杨坚带着酒菜前往。宇文招将杨坚引到寝室，儿子宇文员、宇文贯和妻弟鲁封等都在左右陪侍，佩刀而立，又将兵器暗藏帷幕与宴席之间，埋伏壮士于寝室之后。
杨坚的左右侍卫都不让随从，只有他的堂弟开府大将军杨弘与大将军元胄坐在寝室门旁。杨弘与元胄都以勇力著称，是杨坚的心腹将领。
酒兴正酣时，宇文招不断地用佩刀刺瓜送入杨坚口中，想借机刺杀他，元胄见状，上前对杨坚道：“相府有事，不可久留。”
宇文招呵斥道：“我正与丞相说话，你想干什么！”喝令他退下。元胄动都不动，双目圆睁，怒气冲冲，提刀站在杨坚身旁。
宇文招强挤出一丝笑容，一面赏赐元胄酒喝，一面道：“我难道会有恶意不成！你为何要如此多疑？”又假装要呕吐，站起身想到后房去，元胄担心生变，多次将他扶起坐好。宇文招又谎称喉咙干渴，命元胄到厨房取水，元胄还是不肯离开。正巧滕王宇文逌（音同幽）迟到，杨坚降阶相迎。
元胄乘机对杨坚道：“事有异常，请赶快离开这里！”杨坚道：“他没有掌握兵权，能有什么作为！”元胄道：“军队本来就是皇室的，如果他先发制人，一切都完了。我并不怕死，只是怕死而无益。”杨坚不以为然，仍旧入坐。
不一会儿，元胄听到寝室后面有士兵穿戴甲胄的声音，他立即上前对杨坚道：“相府公事繁忙，您怎能如此畅饮呢！”将他扶下座床快步离去。
宇文招想要追赶杨坚，元胄用身体堵在门口不让他出去。等到杨坚出了大门，元胄才从后面赶上，没能及时下手，宇文招后悔得弹指出血。
七月二十九，杨坚诬陷宇文招与越王宇文盛谋反，杀了他们以及儿子，并重赏元胄，赏赐数不胜数。之后，北周宗室诸王又多次想暗杀杨坚，由于都督李圆通的保护才得以幸免于难。
韦孝宽率军抵达永桥城后，诸将都请求先攻打此城，韦孝宽道：“永桥镇城虽小却很坚固，如果攻而不克，就会挫伤我方军威。只要打败了尉迟迥的大军，这个小城还能有什么作为呢？”于是在武陟（音同至）安营扎寨。
尉迟迥派儿子尉迟惇率军十万进至武德，在沁水东面安营扎寨。时逢沁水暴涨，韦孝宽与尉迟迥的军队隔水相持，一时都无法发起进攻。
这时，韦孝宽府中长史李询秘密向杨坚报告道：“梁士彦、宇文忻和崔弘度三位行军总管接受了尉迟迥馈赠的金钱，因此军中不安，人心异常。”
杨坚深为担忧，与内史上大夫郑译商议派谁取代他们，李德林道：“您与他们本来都是国家重臣，地位平等，他们没有服从您的义务，您现在只是凭借挟天子以令诸侯的权威来控驭他们罢了。您若疑心他们怀有异心，那么往后再派遣的又怎能知道他们会忠于您呢？再说，他们收取尉迟迥馈赠的事真假不明，如果马上派人取而代之，他们可能会因害怕而逃走；如果把他们都抓起来，那么前线将帅自韦孝宽以下都会人人自危。以我看来，您只要派一位既是您的心腹，又通晓谋略，向来为诸将所信服者到军中监视他们的举动。他们即使怀有异心也不敢轻举妄动，万一有异动也必能将其制服。”
一语惊醒梦中人，杨坚连忙道：“如果不是你，几乎要败坏大事。”于是命少内史崔仲方前去监察诸军，并有权节制军事行动，崔仲方推辞不肯去。
杨坚又先后命刘昉和郑译前往，刘昉以自己没有做过将帅为由推辞，郑译也以母亲年迈需要侍奉为由推辞，杨坚心里很不爽。
这时，丞相府司录高熲毛遂自荐，杨坚大喜，就派他前往。高熲接受任命后立即出发，只派人向母亲告别。
从此以后，凡处理军务，杨坚都要与李德林商量。当时，丞相府的军书日以百计，李德林往往同时向几个人口授批文，文意多种多样，从不需要修改。
益州总管王谦也不愿依附杨坚，出动巴蜀军队攻打始州。新任益州总管梁睿到汉川后无法继续前进，杨坚便以梁睿为行军元帅讨伐王谦。
也许是不看好尉迟迥，司马消难起兵后，又向南陈投降，并派儿子司马永入朝为质，请求陈顼的援助。
八月初六，陈顼任命司马消难为大都督、总督九州八镇诸军事、司空，并赐爵随公。八月初七，又让镇西将军樊毅督沔、汉诸军事，命南豫州刺史任忠率军向历阳进发，以超武将军陈慧纪为前军都督，率军向南兖州进发。
八月十五，陈顼又以司马消难为大都督水陆诸军事。八月十七，通直散骑常侍淳于陵率军攻克临江郡，吹响了趁火打劫的号角。
尉迟迥尚未平定，南陈又加入战局，短短数月之间，局势一波三折，也越发的扑朔迷离，对于杨坚来说，夺取大权并不难，难的是如何守住。后人都说杨坚得天下最易，其实哪里真的那么容易呢，每一步都走得险象环生。
