之后，杨广又招募能够沟通极远地方关系的人，广为出使各国。

屯田主事常骏等人请求出使赤土国，杨广非常高兴，命令常骏携带着财物五千段，用来赏赐赤土国王。而赤土国，已经是后世的马来西亚地区了。

常骏等人到达赤土国的国境，赤土国王利富多塞派遣使者乘三十只大船来迎接他们，进献金锁以缆常骏的船。常骏等人在海上渡了一百余天，入赤土境后又过了一个多月，才到达赤土国的国都。赤土国王居住的宫殿、器物用品，都极其珍贵华丽，接待使者的礼节也十分隆重。国王还派儿子那邪迦跟随常骏入朝进贡。

但终究这些事情不能天天发生，所以杨广仍旧需要寻找新的目标。

正巧原本向大隋投降的吐谷浑可汗慕容伏允反悔，杨广接到消息大怒，乃下令征讨吐谷浑。

吐谷浑原本是一个人的名字。吐谷浑，乃鲜卑人，姓慕容，即历史上有名的燕国慕容氏那个慕容。他本是十六国时期前燕政权建立者慕容皝之父慕容廆的庶长兄。其父慕容涉归分部落一千七百家以隶之。后来其父死后，慕容廆要吞并兄长的部落，慕容吐谷浑乃西逃入青海之地。

吐谷浑的孙子叶延，在沙州（今青海省贵南县穆克滩一带）建立慕克川总部，设置司马、长史等官。以祖父吐谷浑为其族名，从此，吐谷浑由人名转为姓氏和族名。

吐谷浑传承了十几代，到了隋朝，已经是河源地区最大的部落。其最庞大的时候，吐谷浑部得据甘、青间，实控东至洮河、龙固（今四川省松潘），西达赤水、白兰，北界黄河，南至大积石山的广大区域。

到了北周时期，吐谷浑王慕容夸吕定都伏俟城，并开始称可汗。

慕容夸吕传子慕容世伏，娶隋朝光化公主为妻。不久，慕容世伏死，弟慕容伏允立，依照风俗，仍以公主为妻。

历史上吐谷浑要到唐朝时期被吐蕃击败内附，直到八世纪末湮没于历史之中，再无痕迹。后世金庸大侠在的小说《天龙八部》之中，意图恢复燕国的大反派慕容复，其名字除了时时提醒自己复国称帝，也是因为这是慕容家族最后一代王者的名字。吐谷浑最后一位乌地野拔勤豆可汗，大唐长乐州都督青海国王便是叫慕容复，慕容复之后，封嗣绝矣。