武德二年（619年）三月，刘武周在突厥支持下举兵南下，尉迟恭也在其中。九月，刘武周占领太原。尉迟恭随宋金刚继续南下，攻克晋州。十月，又攻占浍州。此时夏县人吕崇茂起兵响应刘武周，击败唐右仆射裴寂。李渊诏令永安王李孝基、工部尚书独孤怀恩、陕州总管于筠、内史诗郎唐俭等率兵讨伐吕崇茂。双方对峙于夏县。
是月，秦王李世民奉命统关中兵进攻刘武周。十一月，李世民率军自龙门关乘坚冰过黄河，屯兵柏壁，与宋金刚军对峙，并同固守绛州的唐军形成犄角之势，进逼宋金刚军。十二月，吕崇茂向宋金刚求援，宋金刚即遣尉迟恭和寻相率兵潜往夏县，接应吕崇茂。尉迟恭与吕崇茂里应外合，夹击唐军，大败唐军，李孝基、独孤怀恩、于筠、唐俭及行军总管刘世让全部被尉迟恭俘获。唐高祖李渊为救回被俘诸将，便免去其罪，派人招降了吕崇茂，拜夏州刺史。同时还让吕崇茂暗中除掉尉迟恭，尉迟恭闻讯后，将吕崇茂杀死。尉迟恭、寻相击败唐军后，还军浍州。李世民闻讯后，即派兵部尚书殷开山、总管秦叔宝等在美良川（今山西夏县北）截击尉迟恭军，尉迟恭毫无准备，被唐军斩首二千余级，大败而归。
不久，尉迟恭、寻相秘密率精骑前往蒲坂，救援王行本。李世民又亲自率步骑三千连夜从小路赶到安邑，截击尉迟恭、寻相军，尉迟恭这次败的更惨，除自己与寻相只身脱逃，其众全部被唐军所俘。唐将独孤怀恩也乘机逃走。当时独孤怀恩本欲反唐自立，在狱中曾将此事告诉了唐俭，独孤怀恩逃回后，又奉命攻蒲坂。唐俭闻讯后，恐独孤怀恩反唐，便说服了尉迟恭允许他派人给李渊报信。李渊遂将独孤怀恩诛杀。由此可看出尉迟恭当时已有归唐之心。
武德三年（620年）四月，与唐军相持约5个月的宋金刚军终因粮秣断绝，被迫以寻相部为后卫，向北撤退。李世民即率军跟踪追击，大败宋金刚军。宋金刚率余部2万精兵退至介休（今山西介休），出西门而战，宋金刚惨败而逃。刘武周放弃并州（治晋阳，今山西太原）与宋金刚逃往突厥，后为突厥所杀。尉迟恭则收拢残兵，坚守介休。李世民知其武勇出众，便派任城王李道宗和宇文士及进城劝降。尉迟恭遂与寻相以介休、永安（今山西霍县）二城降唐。李世民见尉迟恭来降，非常高兴，任命尉迟恭为右一府统军，让他继续统领旧部八千人，与诸营相参。李世民的过分信任引起唐军众将的不满，李世民行军元帅长史屈突通怕尉迟恭会反复，多次向李世民提起此事，均被李世民拒绝。
勇冠三军
武德三年（620年）七月，李世民奉命率军东征割据洛阳的郑帝王世充。九月，寻相和刘武周手下的一些旧将相断叛变逃走，唐朝诸将对尉迟恭也怀疑起来，认为尉迟恭必叛，就把其关押在军中。
行台左仆射屈突通、尚书殷开山都说：“尉迟敬德刚刚投降，思想感情还没有归顺。这人非常勇猛剽悍，关押的时间又长，已被我们猜疑，必然产生怨恨。留着他只怕会留下后患，请立即杀了他。”李世民说：“我的看法跟你们不同，尉迟恭如果怀有叛离意图，怎么会在寻相之后呢？”当即命令释放，带进自己的卧室，赏赐给他金银珠宝，对他说：“大丈夫凭着情感志向互相信赖，不必把小小委屈放在心上。我终究不会听信谗言去迫害忠臣良将，您应体谅。一定认为应当离开，现在就用这些东西资助您，表达我们短暂共事的情谊。”
这天，尉迟恭陪同李世民到榆窠打猎，碰上王世充带领几万步兵骑兵前来挑战。王世充的骁勇将领单雄信带领骑兵直奔李世民冲来，尉迟恭驱马冲上前去，太吼一声，斜刺里一枪把单雄信挑下马来。郑军且战且退，尉迟恭保护李世民杀出包围后，又带领骑兵跟王世充作战，几个回合，郑军狼狈逃散，抓住了郑将陈智略，俘虏手持长矛的骑兵六千人。李世民对尉迟恭说：“正当人们要我相信您必然叛离的时候，上天开导我怎样向人们验证我的判断，特地予以证实，行善得福已验证了，因果回报何等迅速。”特地赐给他金银一箱，此后惠顾日益增加。
尉迟恭善于排除、避开长矛，每当单人匹马冲进敌阵，敌人的长矛一齐刺来，始终不能刺到他，他还能夺过敌人的长矛，回手刺杀敌人。这天，他在敌军的重重包围圈里冲进冲出，畅行无阻。齐王李元吉也善于骑在马上使用长矛，听说尉迟恭也会此道就不以为然，要亲自比试，叫拿掉长矛顶端的刀刃用矛杆刺杀。尉迟恭说：“即使安上刀刃，也刺不着我，请您别拿掉，我的当然要拿掉刀刃。”李元吉终究没有刺到他。李世民问他“：夺取长矛、避开长矛，哪种难些？”尉迟恭回答说“：夺取困难些。”于是命令他表演夺取李元吉手中的长矛。李元吉手执长矛长驱骏马，一心想刺着他，尉迟恭没一会儿工夫就一连三次夺得了李元吉的长矛。李元吉一向骁勇，虽然口里赞叹，心里却深深感到耻辱。
李世民由于长年在外征战，所以选千余精锐骑兵作为亲兵，皆着黑衣黑甲，号称玄甲队。每次冲锋陷阵，李世民都披上黑甲亲率玄甲队作为先锋，伺机进击，所向披靡，敌人畏惧。尉迟恭归唐后，与骁将秦叔宝、程知节、翟长孙共同统领玄甲队，保护李世民。
破郑灭夏
武德四年（621年）正月，屈突通与赞皇公窦轨带兵巡营，猝与王世充军遭遇，交战不利，李世民即率玄甲队驰赴救援，大败王世充军，俘其骑将葛彦璋，斩俘六千余人，王世充逃回洛阳。
三月，夏王窦建德率10 余万大军西援洛阳，水陆并进，与王世充部将郭士衡数千人会合，进屯虎牢关东广武山，并在板渚筑宫，与王世充相呼应，威胁唐军侧背。李世民命齐王李元吉等继续围困洛阳，亲率精兵步骑三千五百人于二十五日进驻虎牢。二十六日，李世民率骁骑五百出虎牢，在其东二十多里处侦察窦建德军营，沿途设伏，令李勣、程知节、秦叔宝分别统领。然后与尉迟恭仅带四骑继续前进。李世民对尉迟恭说：“我拿着弓箭，你手持马槊相随，即使有百万大军又奈我如何！”又说：“贼人见到我就返回，这是上策。”
