就这样，裴行俭靠临时借来的一千兵马，以及几位朋友（四镇酋长）的帮助，果然近乎以一己之力降服了两大西突厥余孽。事后，裴行俭上奏朝廷，建议重修碎叶城，以取代焉耆，辟为新的安西四镇之一（从此唐朝的安西四镇为碎叶、龟兹、于阗、疏勒四镇。）；自己便准备押着两位叛贼首领回朝复命。随他一道前来西域的波斯王子急了：“将军，您若是就此回国，那小王的复国之事怎么办？”
“波斯太远了，而且我大唐暂时无意与大食（唐朝称呼阿拉伯人为黑衣大食）交恶。你去吐火罗吧，到了之后，让他们首领划一地给你建国，以招揽贵国的臣民，本官只能帮你到这了。”
“吐火罗的首领若不让小王入境，甚至派兵驱逐我怎么办？”
“你带我的亲笔书信前去，他们见是我裴行俭的主意，一定不会为难你的。”
（吐火罗，是唐朝时期对今天的阿富汗北部二十七国的统称，原先隶属于西突厥。西突厥灭亡后，吐火罗各国首领改向唐朝称臣，波斯王子泥涅师到吐火罗后，招揽得波斯臣民数千人奉他为王，终未成气候。泥涅师晚年，阿拉伯人开始向吐火罗一带进军，泥涅师只得重新逃回长安，病逝于此。）
很显然，裴行俭失信了，波斯王子的“复国梦”没有真正实现。不过这也怪不得裴行俭，他前脚才用计平定了西突厥，皇帝催促他回朝的诏书后脚已经送到。
“爱卿孤身前往万里之外，不用作战就降服了两大叛贼，且建议修筑碎叶城一事，亦极有远见，可谓文韬武略集于一身了。为嘉奖你此战的大功，朕决定让你同时担任文臣、武将两种官职，自大唐开国以来，获得这样殊荣的大臣屈指可数，可见朕对你的器重了…你快回朝吧，东突厥之乱还等着你前往平定呢！”
你看，裴行俭哪有工夫陪波斯王子继续前往中亚，他于八月平定了西突厥叛乱，该年十一月，他一到长安，马上被唐高宗任命为定襄道行军大总管，兼任礼部尚书、检校右卫大将军，又派他去打东突厥，着实忙得很！
唐高宗也是没办法，与西突厥叛军需要依附于吐蕃，不敢单独与唐朝为敌不同，东突厥这时正连战连捷，士气如虹，其打败萧嗣业后，不但单于都护府辖下的二十四州已集体被东突厥叛军收复，甚至连阴山南麓的战略要地：定州，都险象环生，东突厥昔日的两个小弟契丹和奚，见状也跟着凑热闹，与东突厥叛军达成了联盟，一时间，俨然有突厥帝国重新崛起之势。正因此战难度与上一战不可同日而语，已见识过裴行俭所学兵法精妙的唐高宗不但正式授予他元帅头衔（上一战名义上仅是使者），且为他配备的兵力多达三十万人，其中，约十八万军队直接受裴行俭指挥，是为中路军；在其麾下，另有两位副统帅，分别是西路军将领，丰州都督程务挺；东路军将领，幽州都督李文。这二人也各有兵马数万，皆受裴行俭调度指挥。
唐高宗把国运押在了裴行俭一人身上，这是一场没有任何退路的战争，再败，则大唐危矣！裴行俭亦知重任在肩，领命之后不敢有丝毫怠慢，第一时间求见萧嗣业—萧嗣业战败归来，和薛仁贵一样，先被免除官职，后又被判作流放桂州，正坐着囚车准备上路。见裴行俭前来询问自己战败的原因，萧嗣业心有余悸地叹道：“将军有所不知，我出战之时，也自谓兵多将广，又得回纥等部助拳，本无战败之理。起初，我接连获胜，只道叛乱已可轻易平定，不料突厥人之后使用诡计，竟不再率主力与我列阵交战，而是频繁出动小队轻骑，四处打劫我军粮草。我军在塞外作战，粮食都需从中原运来，因敌军神出鬼没，我军粮草屡屡被劫，加上塞外又恰好下起大雪，我军士兵饥寒交加，高昂的士兵逐渐低落。此后，我为了确保粮道畅通，被迫分出大量的兵力去保护运粮车队，哪知突厥人见我把兵力拆散，很快也改变策略，又改为集合主力前来劫营。我从没遇到过这么狡猾的敌人，于是才被打得大败而归，幸得陛下仁慈，免了我的死罪。我能提醒将军的就这么多，希望您能替我报战败之仇啊！”
第二年春季，裴行俭万事俱备，总督三路大军出征，三十多万兵马，旌旗连绵上千里，按裴行俭指示，先到朔州集合，然后统一出关。此朔州，即之前的马邑郡，过了此地，唐军便进入了东突厥叛军的势力范围。
东突厥闻知大唐又派人前来平叛，亦在商量对策。阿史那泥熟匐、阿史德温傅、阿史那奉职三位首领分析过后，认为唐军此战出兵虽众，同样不难对付。一来，他们的兵力也不少，甚至超过裴行俭的兵力；二来，他们已经有了打败唐军的经验，认为只要故伎重演—先分兵断唐军粮道，然后等唐军为守护粮道兵力分散之后，再集合重兵与之决战，就能确保胜利。于是，裴行俭等人方到朔州，关外的突厥骑兵就忙碌起来，只等发现唐军的粮车，就好劫为己用。他们的努力盯哨没有白费，不久后，裴行俭的主力大军离开了朔州，朝着单于都护府方向行进；紧随其后的，是一支由三百辆粮车组成的运粮队伍，仅有数百人护送。三位突厥首领得知此事，喜从心来，忙派出数千骑兵绕过唐军主力，前往劫取粮车。
突厥人的计策再次得逞，押送粮车的唐军见呼啦啦一下子来了十倍多的敌人，撇下车子一哄而散，突厥人也不追赶，美滋滋地把三百辆粮车全部拉到了自己营地附近，然后从容解鞍下马，准备把车里的粮食运到营内。这时，突然有上千支箭朝他们射来，抢粮的突厥骑兵措不及防，许多人中箭倒地；紧接着，只见盖在那些粮车上的篷布自行掀开了，一千五百唐军士兵从车里鱼贯而出，他们撇下手中的弓箭，有的拔出腰间的佩刀，对着刚解除武装的突厥人好一通乱砍；有的人则取出军号，猛力吹奏。“不好，这些根本不是粮车，咱们中计了！”突厥人哪想到会有这样的变故，刚想通知首领，在附近游弋的数万唐军得军号声告知准确方位，又火速赶来支援，他们配合之前的一千五百伏兵，成功将敌军包围。不一会儿工夫，突厥人的大营附近就丢下了数千具尸首，抢粮的那些人几乎全部被唐军杀死。等及三位突厥首领得报，匆忙间想集合军队出营作战时，唐军奉裴行俭事先下达的命令，早骑着抢来的战马逃远了。
突厥人偷鸡不成蚀把米，一粒粮食没抢着，反倒牺牲了数千人，丢了数千匹好马，之后，他们再也不敢靠近唐军的粮车，就算是真的粮车送到他们面前，他们也不抢—谁知道里面藏没藏人。因此，裴行俭无须分兵看守，粮道自然畅通无阻，他的三十万大军也于一日夜间，顺利地抵达了单于都护府附近。单于都护府是座坚城，当初，萧嗣业战败逃回了关内，其副将花大智、李景嘉二人召集败兵坚守都护府，这时该城依然还在唐军手中。三十万唐军连日奔走，俱已疲乏，哪怕他们距离都护府只剩下数十里行程，说什么也不肯再走了，非得就地扎营，待天亮了再去都护府与其他唐军会合。裴行俭仰望星空许久，没有反对，只是提出了一个要求：“诸位辛苦一下，再往前多走五里地。”
这个要求并不过分，但两位副统帅心想：五里地这点短短的路程，走与不走有啥区别？便推诿说营地既已设下，士兵们也都已安顿好了，不可以再移动。哪知刚才还好言好语和他们商量的裴行俭一下子变得暴怒起来：“要么多走五里地，要么今夜到单于都护府集合，没有第三个选择！这是军令！”程务挺、李文没想到裴行俭会为了这点小事拿军令处置他们，哪还敢再说个不字，急忙催促那些已脱去盔甲，准备睡觉的士兵们把盔甲重新穿起来，“奉总管大人军令，全军继续前进，再多走五里地，然后方可扎营！”士兵们嘟哝着嘴，一边抱怨裴行俭没事找事，一边不甘心地穿起盔甲，依主帅命令，又把营地向前推进了五里。当夜，营外狂风交加，大雨瓢泼，下了一整夜的暴风雨。等天亮之后士兵们走出帐篷一看，无不瞠目结舌—昨晚他们一开始打算扎营的地方是个凹地，已水深达一丈多，如同一个小湖泊；而他们后来扎营的地方因为多走了五里，位于高处，大家才侥幸逃过了一劫。将士们这才醍醐灌顶，终于领悟了裴行俭为什么要逼迫他们多走几里地，大家既惊喜又佩服，忙请教裴行俭他为什么会猜到这个结果。裴行俭笑道：“这时你们知道感谢我了？—今后只管服从本帅的命令就是，不必问我是怎么想到的。”