唐高宗准其所奏，遂册立泥洹师为波斯王，命裴行俭为安抚大食使，肃州刺史王方翼为副，检校安西都护。
裴行俭于是以六十一岁高龄奉使出京，再次踏上西域旧守之地，漫漫黄沙之路。
军行旬月，到至陇西。便在穿越莫贺延碛沙漠之时，忽然大风突起，飞沙走石，白昼如同昏夜，连向导亦都迷路，将士饥饿疲劳不堪。
裴行俭见此，便命就此宿营，然后举行祭祀。因虔诚跪拜多番，又侧耳倾听良久，起身传令道：天神明示于我，此处离水泉不远。
将士闻此，半信半疑。此后未久，风平沙落，云开日出。
裴行俭复令拔营起行，走未数百步之遥，便见眼前水泉丰沛，草木繁茂。后军渐渐赶至，皆都互相打听，连向导亦皆惊呆，不知到至何地。
军中便有自谓见闻博广者，对众人言道：某观史书，详此地貌，似是西汉李广利将军取马之时，所至大宛贰师城。
裴行俭恰好来至，闻言大笑道：果然不假，此处正是当年贰师城，此时却唤西州。
各属国官员闻说当年都督府裴大长史将军来到，皆都出城迎接，如同参拜可汗检阅一般。裴行俭对行伍之中部落酋长、旧日衙中僚属逐一点唤其名，众人无不老泪纵横。
入城休歇三日，裴行俭声明君命在身，不可久留，遂从当地招集一千多名豪杰子弟，随从西行。将出发时，裴行俭复又扬言天热不可远行，待天气稍凉，方可西上波斯。
阿史那都支早派细作在西州城中，闻听回报，信以为真，由此不为防备。
遂遣使与李遮匐相约：汉使即说待秋后乘凉西去，彼时我可齐集大军，聚而歼之。
裴行俭明知城内必有突厥细作暗探，遂故作随意召请四镇豪酋故友相见，纵言当年常在一起纵猎甚欢，欲趁此重回旧地之便，请大家再出城会猎。
诸胡人子弟皆喜裴行俭豪放，闻听此言，争请从猎，纷纷报名。三五日后，得远近万人报名参加会猎，皆都是族中青壮之士，骑射能手。
裴行俭于是佯为畋猎，到城外沿途整队，吸纳陆续参加与会者，率众一路西进。离阿史那都支部落十余里，便有随从说道：前面已是十姓可汗金帐，将军不可再往前行