上元二年,加银青光禄大夫。高宗以行俭工于草书。尝以绢素百卷,令行俭草书《文选》一部,帝览之称善,赐帛五百段。行俭尝谓人曰:“褚遂良非精笔佳墨,未尝辄书,不择笔墨而妍捷者,唯余及虞世南耳。”三年,吐蕃背叛,诏行俭为洮州道左二军总管。寻又为泰州镇抚右军总管,并受元帅周王节度。
仪凤二年,十姓可汗阿史那匐延都支及李遮匐扇动蕃落,侵逼安西,连和吐蕃,议者欲发兵讨之。行俭建议曰:“吐蕃叛涣,干戈未息,敬玄、审礼,失律丧元,安可更为西方生事?今波斯王身没,其子泥涅师师充质在京,望差使往波斯册立,即路由二蕃部落,便宜从事,必可有功。”高宗从之,因命行俭册送波斯王,仍为安抚大食使。途经莫贺延碛,属风沙晦暝,导者益迷。行俭命下营,虔诚致祭,令告将吏,泉井非遥。俄而云收风静,行数百步,水草甚丰,后来之人,莫知其处。众皆悦服,比之贰师将军。至西州,人吏郊迎,行俭召其豪杰子弟千余人随己而西。乃扬言绐其下曰:“今正炎蒸,热坂难冒,凉秋之后,方可渐行。”都支觇知之,遂不设备。行俭仍召四镇诸蕃酋长豪杰谓曰:“忆昔此游,未尝厌倦,虽还京辇,无时暂忘。今因是行,欲寻旧赏,谁能从吾猎也?”是时蕃酋子弟投募者仅万人。行俭假为畋游,教试部伍,数日,遂倍道而进。去都支部落十余里,先遣都支所亲问其安否,外示闲暇,似非讨袭,续又使人趣召相见。都支先与遮匐通谋,秋中拟拒汉使,卒闻军到,计无所出,自率兒侄首领等五百余骑就营来谒,遂擒之。是日,传其契箭,诸部酋长悉来请命,并执送碎叶城。简其精骑,轻赍晓夜前进,将虏遮匐。途中果获都支还使,与遮匐使同来。行俭释遮匐行人,令先往晓喻其主,兼述都支已擒,遮匐寻复来降。于是将吏已下立碑于碎叶城以纪其功,擒都支、遮匐而还。高宗廷劳之曰:“比以西服未宁,遣卿总兵讨逐,孤军深入,经途万里。卿权略有闻,诚节夙著,兵不血刃,而凶党殄灭。伐叛柔服,深副朕委。”寻又赐宴。谓行俭曰:“卿文武兼资,今故授卿二职。”即日拜礼部尚书,兼检校右卫大将军。