尉多侯年轻时有武艺才干，继承爵位为渔阳王。显祖
拓跋弘时，任假节、征西将军、兼护羌戎校尉、敦煌镇将。到镇所，上奏疏请求率领轻装的骑兵五千人，向西进入于阗，兼并各国，利用敌人取得物资，直至全部平定。显祖不准许。
高祖
元宏初年，
柔然部落首领无卢真率领三万骑兵进入边境包围军镇，尉多侯击退了他，因功劳升军号为征西大将军。
尉多侯在南山狩猎，柔然派遣部落首领度拔进军包围敦煌，截断尉多侯的退路。尉多侯一边前进一边作战，于是冲出包围而进城。率领军队出城交战，大败度拔，追击几十里，斩首一千多级。
上疏请求攻取
伊吾，断绝柔然通向西域的道路。高祖认为他的计策好，因春耕正进行，感到为难。