尉迟运，是大司空、吴国公尉迟纲的儿子。
从小精强干练，有志功名。
魏大统十六年(550)，由于父亲的功勋而封为安喜县侯，食邑一千户。
孝闵帝登基，授使持节、车骑大将军、仪同三司。
不久，孝闵帝被废，朝中议论，打算拥立世宗，于是命令尉迟运前往岐州奉迎。
由于参与拥立皇帝有功，晋封周城县公，食邑增加五百户。
保定元年(561)，升任骠骑大将军、开府仪同三司。
三年，跟随杨忠进攻齐国的并州，由于有功，另封其第二子尉迟端为保城WWW.sLKj.oRg县侯，食邑一千户。
四年，出任陇州刺史。
该州被水、渭水环绕，百姓难以治理。
尉迟运关心百姓，安抚收容，当时甚有美名。
天和五年(570)，入朝任小右武伯。
六年，升任左武伯中大夫。
随即加军司马衔，武伯职务不变。
尉迟运兼任文武官职，很被重用。
齐国将领斛律明月侵犯汾水以北，尉迟运跟随齐公宇文宪防守，攻占伏龙城。
晋封广业郡公，食邑增加八百户。
建德元年(572)，授右侍伯，转任右司卫。
当时宣帝在东宫，亲近小人，多有罪过。
高祖从大臣里挑选忠直刚正者去辅佐他，于是任命尉迟运为右宫正。
三年，皇帝驾幸云阳宫，又命令尉迟运以原任官职兼任司武，与长孙览辅佐皇太子留守。
不久，卫王宇文直叛乱，率领党徒袭击肃章门。
长孙览害怕，逃向云阳宫。
当时，尉迟运偶然在宫门内，宇文直的士兵突然杀到，尉迟运来不及命令别人，就亲自关门。
宇文直的党徒与尉迟运争夺宫门，砍伤尉迟运手指，但宫门还是勉强关上。
宇文直无法入宫，就放火烧宫门。
尉迟运担心火灭之后，宇文直党徒即可进宫，就取来宫中木材以及床等物品，增大火势，又浇上油脂，火势更盛。
过了很久，宇文直无法进宫，只得退兵。
尉迟运率领留守士兵，乘机进击，宇文直大败而逃。
这一天，如果没有尉迟运，皇宫早已失守。
高祖嘉奖他，授大将军，把宇文直的田宅、妓乐、金帛、车马以及杂物等，赏赐给尉迟运，数量多得无法计算。
四年，出任同州、蒲津、潼关等六防诸军事、同州刺史。
高祖打算讨伐齐国，调尉迟运参加商议。
平定东部，出力不小。
五年，授柱国，晋封卢国公，食邑五千户。
宣政元年(578)，转任司武上大夫，总管宿卫。
高祖在云阳宫驾崩，秘不发丧，尉迟运率领侍卫兵返回京师。
宣帝即位，授上柱国。
尉迟运从前担任宫正时，曾多次规劝宣帝。
宣帝不能接受，反而对他疏远忌恨。
当时尉迟运又与王轨、宇文孝伯等人都是高祖近臣，王轨曾多次把宣帝的过失告诉高祖。
宣帝认为尉迟运参预了这件事，对他更加忌恨。
王轨被处死以后，尉迟运害怕灾祸降临到自己头上，向宇文孝伯询问对策。
事见《孝伯传》。
不久，出任秦州总管、秦渭等六州诸军事、秦州刺史。
但是尉迟运到秦州以后，仍然害怕逃不脱灾祸。
大象元年(579)二月，因忧惧在秦州去世，当时四十一岁。
追赠大后丞，秦、渭、河、鄯、成、洮、文等七州诸军事，秦州刺史。
谥号为“中”。
儿子尉迟靖承袭爵位。
大象末年，官至仪同大将军。