郡公。大统十五年，他又迁升为尚书左仆射，兼领军将军。他通脱敏捷，颇有才干。虽然职兼文武，却颇负时望，宇文泰因此很重用和依仗他。大统十六年，他被封为大将军。

侯景背魏渡江投奔南梁，梁元帝当时镇守江陵，请求与邻国修好。他的弟弟武陵王萧纪在蜀称帝，率军东下，将要攻打江陵。梁元帝大为恐惧，送信给西魏请求救援。宇文泰说“：蜀地可以图取呀！占据蜀地，制服梁朝，在此一举。”便与朝臣们议论，将领多持不同意见。惟有尉迟迥认为萧纪既然率所有的精锐部队东下，蜀地一定空虚，西魏军队到来后，一定会有征无战。宇文泰认为他分析得正确，对他说：“伐蜀的事情完全委托给你。”于是，命他率开府元珍、乙弗亚、侯吕陵始、叱奴兴、綦连雄、宇文升等六军将士攻取晋寿，开辟平林旧道。尉迟迥的前军到达剑阁，安州刺史乐广献出州城率先投降。萧纪的梁州刺史杨乾运这时镇守潼水，早已派使者到西魏朝廷，秘密送上降表。然而恐怕他的部下不同意，仍占据潼水安营把守。尉迟迥派元珍、侯吕陵始等发起进攻，杨乾运退回潼川。元珍等人领军将他包围，乾运投降。尉迟迥到达潼川，大肆犒劳全军将士，然后渡过涪江，来到青溪，登上南原，将军队驻扎下来讲解兵书，制定规约，修整器械，自开府以下的将士奖赏金钱布帛数量各有不同。这时，正值盛夏阴雨连绵，山路险峻难行，将士们疲惫生病的十有二三。他亲自慰问，送去汤药，率军西进。纪益州刺史萧扌为固城自守，尉迟迥派兵将他包围。当初，萧纪到巴郡，派前梁州刺史史欣景、幽州刺史赵拔扈等人作为萧扌为的外援。尉迟迥分别派遣元珍、乙弗亚等人将他们打败。赵拔扈等逃跑，史欣景投降。萧扌为被包围五十来天，双方多次交战，终被尉迟迥将益州攻破。萧扌为派人请降，尉迟迥答应了他。萧扌为便与萧纪的儿子宜都王萧圆肃率领文武官员到尉迟迥的军帐前求见，他按礼节接见他们，让官吏们各恢复旧职，只没收他们的奴仆和储蓄的财产，以犒赏西魏将士。他的军队号令严明，将士们没有私心。朝廷下诏命他为大都督、益潼等十二州诸军事、益州刺史。废帝三年(554)，增加督管六州，加上原来的共十八州诸军事。因平蜀的功劳，朝廷加封他的一个儿子为安国郡公。自剑阁以南，他可以根据朝廷制度封位和降免官吏。他赏罚分明，布植恩泽和威信，安抚新取得的土地上的百姓，经营那些暂时没有归附的地方，汉人和夷族的百姓都怀念并归顺他。

他的性情十分孝顺，对父母奉养从不懈怠，自己虽经常在外，然而得到四季的新鲜食品，一定先奉献给父母，然后自己才敢吃。他的母亲大长公主年迈多病，过去在京城，每次退朝他都去侍奉母亲的起居，忧虑的神情形于脸色。大长公主每次都和颜悦色地进食，以宽慰儿子的心。宇文泰知道他的性情，将他调回朝中，以宽慰他母子二人的心情。并派大鸿胪的官员到郊外去迎接慰劳他，赐给他公侯用的衮衣和冠冕。他离开后，蜀人思念他，为他立碑歌颂功德。文官制度刚实行，他被封为小宗伯。

周孝闵帝即位，晋封他为柱国大将军，因他有平蜀的功劳，仿效汉代霍去病冠军的意思，改封他为宁蜀公。又迁任为大司马。不久，以现有的官职镇守陇右。武成元年(559)，朝廷又晋封他为蜀国公，食邑一万户，任秦州总管、秦渭等十四州诸军事、陇右大都督。保定二年，封他为大司马。晋公宇文护东伐，他率军进攻洛阳。齐王宇文宽等人驻扎在邙山，齐军渡过黄河，周军因惊慌四散逃去。他率本部人马一边退却一边反击敌人，于是周军可以完整地退回。他又迁任太保、太傅。

宣帝即位，命他为大右弼，出任为相州总管。宣帝驾崩，杨坚辅助朝政，杨坚认为尉迟迥位高望重，担心他会谋图反叛，便命他的儿子魏安郡公尉迟。。带上诏书，以参加宣帝的葬礼为名征调他回京。不久命郧国公韦孝宽代替他任相州总管。他因杨坚当权图谋篡夺皇位，便密谋举兵起事。他留下尉迟。。而不接受韦孝宽代理。杨坚又命侯正破六韩裒到尉迟迥那里宣读圣旨，暗中给总管府长史晋昶等人书信，命他早作准备。尉迟迥听说后，杀掉晋昶，召集文武官员等登上州城的北城楼而号令他们。于是，大家都乐于从命，无不感激奋发。他自称大总督，根据制度设置官司。这时，赵王宇文招已经入朝，留下小儿子在封国守卫，尉迟迥又奉他的号令。尉迟迥兄弟的儿子、大将军、成平郡公尉迟勤这时任青州总管，最初收到尉迟迥要他举兵响应的书信，他送给了朝廷，不久，又随尉迟迥起事。尉迟迥所管辖的相、卫、黎、毛、。。、贝、赵、冀、瀛、沧，和尉迟勤统率的青、齐、胶、光、莒等州一起响应，有军队数十万。荥州刺史邵国公宇文胄、申州刺史李惠、东楚州刺史费也利进国、东潼州刺史曹孝达也各自据守本州响应。永桥镇将纥豆陵惠献城投降。尉迟迥又向北联合高宝宁以与突厥沟通；南面与陈人联合，答应割让江淮之间的土地给陈国。