十二月，吕崇茂军在那么多人的打击下，最终抵抗不住了，只好向宋金刚求援。尉迟敬德和寻相随即被派往夏县援助吕崇茂，并与吕崇茂内外夹击，大败唐军，这次唐军可真是损失惨重，李孝基、独孤怀恩、于筠、唐俭及行军总管刘世让全让尉迟敬德逮到。李渊认为既然硬的不行就来软的，随即派人前往招降吕崇茂，谁知姓吕的早有降意，还表示要除去尉迟敬德作为礼物来求取信任。要说尉迟敬德消息也灵通，不知道从什么地方听到风声，来了个先下手为强杀掉了吕崇茂。
在尉迟敬德的钢鞭之下大唐军队节节败退，李世民怎么看得过去？就在尉迟敬德、寻相击败唐军准备回浍州的途中，李世民派兵部尚书殷开山、总管秦叔宝等在美良川（今山西夏县北）截击尉迟敬德军。因为事出突然，尉迟敬德也没有什么心理准备，被唐军杀了个措手不及，大败而归。不久，尉迟敬德、寻相率精骑秘密前往蒲坂（今山西永济西南蒲州镇），求援事前投奔刘武周的原隋问东守将王行本。真是冤家路窄，李世民又盯上了他，亲自率步骑3000连夜从小路赶到安邑（今山西运城东北安邑），截击尉迟敬德、寻相军。尉迟敬德这次败得更惨，除自己与寻相只身脱逃，手下人全部被唐军掳获。唐将独孤怀恩也乘机逃走，因为当时独孤怀恩就打算反唐自立，在狱中曾将此事告诉了唐俭。独孤怀恩逃回后，又奉命攻蒲坂。唐俭听说后，唯恐独孤怀恩叛唐，便跟尉迟敬德说要写信告诉李渊这件事，没想到尉迟敬德竟然很爽快地答应了。李渊看到信之后核查此事，很快就除去了独孤怀恩。由此可以看出尉迟敬德当时就有归顺唐朝的心思了。
武德三年即公元620年四月，跟大唐军队僵持半年的宋金刚眼看就要吃不上饭了，不得已向北撤兵。李世民一看机会来了，随即率军跟踪并且打败了宋金刚军，饥肠辘辘的宋金刚军战败，宋金刚无奈只好率余部2万精兵退守介休（今山西介休）。后来，冲破包围，狼狈逃脱了。这之后，刘武周损失惨重，在中原再也混不下去了，于是放弃并州（今山西太原）逃亡突厥，后来，很“荣幸”地被突厥杀了。剩下尉迟敬德收拢残余部队，坚守介休。李世民慧眼识英雄，知道他勇武出众，于是派遣任城王李道宗和宇文士及前往招降。尉迟敬德通过这场战争，更加清楚地看清了李世民的为人，而且，自己原先就有归顺唐朝的心思，于是就和寻相以介休、永安（今山西霍县）二城降唐。
李世民多次与尉迟敬德交手，从尉迟敬德连连击败唐军的事实来看，实在是不可多得的一员猛将。李世民惜才心切，更是爱才心切，所以见到尉迟敬德来降，高兴得是忘乎所以，好酒好菜地款待他。不仅如此，李世民还给了尉迟敬德不低的官职，封尉迟敬德为右一府统军，让他继续统领旧部八千人（就是一同在介休投降的那些）。不光如此，对这些降兵降将也不做任何防范。在这件事情上，李世民的过分信任引起了唐军众将的不满。
后来，寻相跟一些原来的将士趁李世民征讨王世充的时候逃走了。于是就有人开始怀疑尉迟敬德也会逃跑。行台左仆射屈突通与尚书殷开山还建议李世民干掉尉迟敬德。李世民没有答应，后来，单独找了尉迟敬德谈话，还拿出一些银子给他。说如果他要谋反，这些银子可以作盘缠。当时尉迟敬德没有表态，但是却在第二天用行动证明了自己对李世民的忠诚。
不善言辞的回报
九月二十一日，李世民带着五百骑兵巡视战场。结果，无巧不成书，在魏宣武陵遇见了带领着大部队的王世充。此时正在给王世充打工的单雄信很想在自己主子面前露露脸，就挥舞着槊直奔李世民而来。说时迟那时快，尉迟敬德大喝一声，就把单雄信从马上刺了下来。单雄信偷鸡不成反蚀一把米，只好退下阵来。
俗话说得好，憨的怕愣的，楞的怕不要命的。尉迟敬德如此武功高强而且不要命，谁敢跟他玩命？王世充的将士直吓得往后退。尉迟敬德正好趁机护卫着李世民杀出重围。后来，二人意犹未尽，又回去杀了个痛快，两个人如入无人之境。后来，屈突通带着大队人马赶到，收拾了这拨人。尉迟敬德活捉其大将军陈智略，杀敌无数，只有王世充一人侥幸逃跑。自此，李世民更加相信自己的判断，而尉迟敬德也渐渐被唐军接纳。
尉迟敬德向来以善于避槊而闻名，经常单骑闯进敌阵之中，敌军很多槊一起刺都伤不了他，而且还能夺取别人的槊返刺别人。这就不是一般的厉害了。
当时李元吉也在李世民的军中，他对自己骑马舞槊的本事也不是一般的自信。听说尉迟敬德这么厉害，李元吉非常不服气，强烈要求跟尉迟敬德切磋武艺。这是人民内部比试，李元吉认为应该去掉槊刃，不能真刀真枪地干。尉迟敬德艺高人胆大，自己把槊刃去掉了，却不让李元吉去掉。
李元吉一看尉迟敬德这么嚣张，更加不服气。但是上场之后，却怎么都刺不到尉迟敬德的身上。观战的李世民问尉迟敬德：避槊和夺槊哪个更难？地球人都知道夺比避要难啊。尉迟敬德也说是“夺槊难”。李世民问完这个看似弱智的问题后，就让尉迟敬德去夺李元吉的槊。
李元吉也是舞槊的行家，看到尉迟敬德要夺自己的槊，也很不服气，于是舞槊跃马，使出了看家本领要刺尉迟敬德。可尉迟敬德实在是太有才了，转眼工夫连续三次从李元吉手里夺走了槊。李元吉表面上非常赞叹，至于心里怎么想，就只有他自己知道了。李世民为什么要问那个有点弱智的问题，又为什么让尉迟敬德去夺李元吉的槊，难道是想让自己亲爱的弟弟李元吉懂得“人外有人、天外有天”的道理？
也许吧！
李世民知人善任，对尉迟敬德更是无比信任。尉迟敬德降唐后，李世民让他与秦叔宝、程知节、翟长孙共同统领玄甲队，专门负责保护李世民。武德四年即621年，唐军围困驻守洛阳的王世充。三月夏王窦建德率领10余万大军来援救洛阳的王世充，水陆并进。李世民率领500精骑从虎牢出发，一面侦查窦建德的军营，一面令李世勣、程知节、秦叔宝分别率一路兵马沿途设伏。而李世民与尉迟敬德则仅带着4名轻骑继续前进，此时的李世民还镇定自若地对尉迟敬德说，他拿着弓箭，尉迟敬德拿着槊，就是敌军有百万之众，也不能把他怎么样。快到窦建德军营的时候，突然遇到了敌军的游骑，李世民不慌不忙，向着敌军大呼“我是秦王！”并且一边呼喊一边引箭射杀敌军，这时候窦建德的兵马好像炸开了锅，匆忙派出五六千人前来追杀李世民。那四名跟着秦王的骑兵吓坏了，心想你李世民的胆子也忒大了，五六个人对五六千人，这不找死呢。李世民面无惧色回头对这四个人说：“你们先走，我跟尉迟敬德殿后。”说是这么说，哪一个士兵敢先走啊。有尉迟敬德的保护，李世民可以说是相当镇定，他似乎对这个降将信任得很，一边撤退一边射杀敌军，直至最后窦建德的军队被引入伏击的地方，唐军出动打败了窦建德军。
当年五月初二，窦建德的军队倾巢而出，擂响战鼓向唐军挑战。战场之上王世充的侄子王琬骑着隋炀帝的骢马招摇过市，炫耀于众。李世民向来喜欢马，看到之后感叹：“这真是一匹好马啊！”尉迟敬德听到后，请求出战表示要把马夺过来。李世民当然不会为一匹马而让心腹大将冒险，但是尉迟敬德决心已下，于是直入窦军，抓到了王琬，抢回了宝马。到中午的时候李世民见窦军饥疲思归，心想时机来了，下令出击，全歼窦军。随后挥师攻打洛阳，王世充见大势已去，被迫投降。
七月，窦建德的老部下刘黑闼起兵反唐，很快占领了河北大部和河南部分地区。十二月，李世民奉命征讨刘黑闼。武德五年即622年三月，刘黑闼率军袭击李世勣军，李世民和李道宗袭击刘黑闼的侧后方来援救李世勣，结果反而被刘黑闼围困了。尉迟敬德知道后，奋勇杀入敌阵，将李世民和李道宗救出。二十六日，唐军大败刘黑闼，刘黑闼逃入突厥。随后，尉迟敬德又随军平定了响应刘黑闼的徐圆朗。这次唐军的大胜，再次证明了李世民的过人眼光，而尉迟敬德也因此次战斗被授予秦王府左二副护军。
唐朝的统一大业基本完成后，北方的突厥恶习不改，仍旧不断南侵，趁着唐朝脚步不稳想要推翻唐朝。尉迟敬德在与突厥的作战中也屡立战功。早在武德四年九月，尉迟敬德便曾击退过突厥军。武德六年（623年）七月初九，突厥侵犯原州。十一日，进攻朔州，右武侯大将军李高迁被击败，尉迟敬德奉命带兵救援。武德七年（624年）七月十二日，突厥袭扰陇州（治汧源，今陕西陇县），尉迟敬德（时任护军）再次奉命进击突厥。
玄武门之变立大功
天下既定，主要矛盾从国外转到了国内。李世民在唐统一大业中屡建奇功，威望日益飙升，逐渐形成了以秦王府谋士和勇将为核心的实力雄厚的政治集团，严重威胁到太子李建成。因此，李建成多次用计想除掉李世民，但偏偏李世民福大命大，每次都转危为安。
李渊看出了端倪，也考虑消灭秦王党羽，却找不到合适的借口，又觉得李世民留在身边也方便处置。这时候李建成和李元吉就开始动手，他们将目标锁定在李世民身边的大将身上。尉迟敬德是他们的首选。李建成这次拉拢也算是下了血本，居然送了一车的金银到尉迟家，比当年李世民笼络敬德时给的那几块金子多多了。没料到尉迟敬德却不吃这套，人家认准了李世民，金子再多也比不上情意重，把东西统统退了回去。不仅如此，后来尉迟敬德还把这事告诉了李世民，也算是表表忠心吧。李世民反倒责怪他说，面对糖衣炮弹，要把糖衣留下，炮弹还回去。现在你这么折他们的面子，估计他们要对付你了。
李世民真是有先见之明。尉迟的举动可把李建成哥俩气坏了，心想你个打铁的真是敬酒不吃吃罚酒。接着他们就派人去刺杀尉迟敬德，尉迟敬德不慌不忙，大门敞开地欢迎刺客，最终刺客被吓跑了。后来，李建成哥俩就诬陷尉迟敬德要谋反，李世民在李渊面前把道理一讲，李渊自知理亏，也就免了尉迟敬德一场无妄之灾。
李建成和李元吉越来越放肆，显示出了要杀李世民的苗头。尉迟敬德为此力劝李世民先下手为强。后来，突厥来袭，李建成和李元吉就想趁机削弱李世民的军队，想要把尉迟敬德等大将抽调过来。这下，李世民终于认识到问题的严重性。在跟李建成喝了一次酒后，李世民差点中毒而死，于是痛下决心，要先下手为强。他先向李渊揭露李建成和李元吉趁李渊不备玩了他的女人，挑起了李渊的怒火，再说他们想要谋害自己的动机。李渊一听，就传二人第二天来宫中对质。
626年六月初四，李世民在李建成、李元吉入宫必经之地玄武门大设埋伏。二人哪知道会有这样的埋伏，或许他们一直都认为李世民做不出这样的事来，于是老老实实地按时入宫，谁知一到玄武门感觉气氛不对，随即转身就跑。李世民的伏击一下子变成了追击，这恐怕也把李世民吓出一身冷汗。幸亏李建成慌乱之下动作迟缓，被李世民一箭射中。李元吉也算身经百战，跑的快，一转眼就跑进了树林。李世民哪肯放过，顺着声音就追过去了，要说李世民也倒霉，一不小心就让树枝扫下了马。李世民还在数着金星的时候，李元吉就赶了过来，夺了李世民的弓，想用弓弦勒死他。说时迟那时快，尉迟敬德在千钧一发之际又成了李世民的大救星。李元吉见是尉迟敬德转身逃跑，但终究跑不过尉迟，可能是马的缘故，也可能是太过慌乱，最终被尉迟敬德追上射杀了。如果不是尉迟敬德及时赶到，李世民死得可就冤咯。
但是太子党还是很有实力的，李建成、李元吉二人也不是没有准备，他们手下的两千余精兵就等候在宫外，得知玄武门内有变就拼了命地攻打，妄图救出他二人。两千人不是小数目，秦王所带的人员又不足。关键时候还是尉迟敬德脑筋好使，砍了李建成、李元吉的脑袋去见那些攻打者，并告诉他们大势已去。这些人见太子都被宰了，自然四散逃离。
事后李世民派尉迟敬德去保护李渊，实际上就是想逼宫。老皇帝正在悠哉地泛舟游玩，等候三个儿子前来对质，突然见尉迟敬德一身戎装，还携带武器来到面前，这可吓傻了李渊，忙问这是怎么一回事。尉迟敬德就说了，太子和齐王作乱，现在被秦王正法了，秦王怕陛下受惊扰，就派我来护驾。李渊心里明白得很，知道大势已去，于是当尉迟敬德要求下旨命令太子齐王部停止反抗的时候，李渊立刻应允。至此，李世民获得了全面胜利，而尉迟敬德居功至伟。
初七，李渊立李世民为太子，尉迟敬德因功被授予太子左卫率。还把李元吉的全部家产赐给了尉迟敬德。
性子憨直得罪人
国内刚刚安定，突厥就趁机打了过来。突厥颉利可汗、突利可汗率领十余万大军直扑长安。当时唐朝的兵力分散，突厥行军速度迅猛，各地援军又来不及赶到。情急之下，李世民派尉迟敬德率精锐骑兵主动出击，来个硬碰硬。两军在长安北七十里的泾阳血战，尉迟敬德勇猛异常，奋不顾身杀入敌阵，攻破突厥的攻势最终得胜而归。损失千余骑兵的突厥在心理上受到重重的打击，原本以为玄武门之变后唐朝时局动荡，可以乘机捡个便宜，谁知偷鸡不成反蚀一把米。接下来李世民又来了一招更绝的——空城计，前辈留下的妙招怎能不用。李世民只带六名骑兵亲自到渭水桥与颉利谈判，还派人给突利可汗做思想工作。结果最终没有发生流血事件，而是定下了便桥之盟。
由于尉迟敬德性情憨直，又自以为功劳大，所以每次见到房玄龄、杜如晦、长孙无忌这些人的时候总是讽刺他们，说他们只是耍嘴皮子，而自己的功劳却是真刀真枪杀出来的，有时候甚至争论到面红耳赤。这样一来，尉迟敬德就同时得罪了相当一部分幕僚，在天下安定的文臣时代，这样的行为实在是不明智的。后来他果然被排挤出京师，先后在襄州（今湖北襄樊）、同州做地方官。