元朝通使南海诸国始于灭南宋之后。至元十四年，元军取福建，南宋主管市舶的蒲寿庚投降，使元朝拥有了通海外的主要港口泉州和大量海舶，以及熟悉海外交通、国情和贸易的人才。次年八月，忽必烈以大将唆都与蒲寿庚并为中书左丞，行省福建，诏命他们：“诸蕃国列居东南岛屿者，皆有慕义之心，可因蕃舶诸人宣布朕意：诚能来朝，朕将宠礼之；其往来互市，从所欲。”（《元史·世祖纪》）十六年末，又命朝臣与唆都商议“招收海外诸番事”，并决定“诏谕海内海外诸番国主”（同上）。

在此之前，唆都已派治中赵玉出使爪哇（十六年十二月还，其出使当在上年底），可能还通过蕃商向其他各国传达了上述欢迎“来朝”和允许自由互市的旨意，于是十六、十七年相继有马八儿、俱兰、爪哇等国遣使来元。十七、十八年，元朝先后派招讨使速剌蛮和苫思丁等出使木剌由国（Malayu，又译没剌由、麻里予儿等，今苏门答剌东部之占碑，此时为三佛齐国都所在，故即指三佛齐国），招讨使杨廷璧等“招抚”海外各国，宣慰孟庆元、万户孙胜夫出使爪哇，展开了频繁的外交活动。

爪哇是当时南海的强国，杜马班（新柯沙里）朝国王葛达那加剌在位时（1254—1292），不仅将西爪哇纳入治下，还征服了马都拉、巴厘岛，并乘三佛齐（木剌由）衰落之机出兵往征，迫使其臣服。因此，元朝“招抚”海外诸国，自然要以爪哇为主要目标。忽必烈认为，只要征服了爪哇，“其余小国即当自服”（《元史·亦黑迷失传》）。自唆都派赵玉出使爪哇以后，元朝又多次派出使臣：至元十七年十月，“遣使谕爪哇国”；十八年十一月，“诏谕爪哇国主，使亲来觐”（诏使应即宣慰孟庆元等）；二十三年七月，“遣必剌蛮等使爪哇”（并见《元史·世祖纪》）。爪哇也有使者前来，并曾进金佛塔（同上书至元十九年七月条）。但后来以右丞孟琪为诏使前往，却被爪哇国王黥面逐回，原因可能是胁迫其亲身入朝，激怒了声威正盛的葛达那加剌。

元朝通使海外的最早记录是至元九年亦黑迷失“奉世祖命使海外八罗孛国。十一年，偕其国人以珍宝奉表来朝。十二年，再使其国，与其国师以名药来献”。（《元史·亦黑迷失传》）。八罗孛国，或以为即印度半岛南端西侧Malabar海岸地带（名见马可波罗和伊本拔图塔行记）。但此时东南沿海港口都在南宋治下，元使何由出海？实属可疑。

《元史·世祖纪》载至元十七年十二月“以奉使木剌由国速剌蛮为招讨使”，十八年六月“奉使木剌由国苫思丁至占城船坏，使人来言，乞给舟粮及益兵”，疑先后所记系同一次出使。又同书载至元十九年七月“宣慰孟庆元.使爪哇回”，九月“招讨使杨廷璧招抚海外，南蕃皆遣使来贡”，此两使出使时间都应在十八年冬或更早。

二十九年，忽必烈以爪哇辱逐诏使为由，遣史弼、高兴、亦黑迷失（皆授福建行省平章）率军士二万，海船五百艘往征（后实际出征军仅五千）。十二月，由泉州启航，三十年二月，抵爪哇北岸之杜并足（今厨闽），马步军登岸陆行，水军仍乘舟进，规定在八节涧（今泗水南）会师，盖因其地上接杜马班，下通大海，“乃爪哇咽喉必争之地”。