朕闻汉人言，取人家国，欲得百姓土地，若尽杀百姓，徒得土地何用？又有一事，朕实忧之，恐卿辈不和耳！
——元世祖忽必烈在元军第二次征日前夕对诸将的训话
根据《元史》的记载，日本进入蒙古帝国大汗的战略视野，最早是在至元二年，也就是公元1265年。当年，高丽人赵彝等人谏言忽必烈“日本国可通”，于是，大汗开始考虑适合出使日本的人选。
公元1266年8月，礼部侍郎殷弘与兵部侍郎黑的奉旨出使。比照元朝（当时忽必烈尚未立国号“元”）的百官级别设置，兵部侍郎、礼部侍郎都是正四品，如果换成现在的官阶，则比正厅级的级别稍高，比副部级的级别稍低。安排两位正四品官员出使，算是比较给一向被称为“倭国”的日本面子了。
由于之前从未与日本打过交道，不熟悉那里的政治地理情况，忽必烈给高丽国王王禃下了一道圣旨，要求他选派合适的向导，协助蒙古特使出访日本。忽必烈在圣旨中警告王禃：“勿以风涛险阻为辞，勿以未尝通好为解……卿之忠诚于斯可见。”至于蒙古与高丽的关系，后文将有专节交代。
在这两位侍郎出发之前，忽必烈交给了他们一封信，让他们转交给日本国王。这封国书原文如下：
大蒙古国皇帝奉书日本国王：朕惟自古小国之君，境土相接，尚务讲信修睦。况我祖宗，受天明命，奄有区夏，遐方异域，畏威怀德者，不可悉数。朕即位之初，以高丽无辜之民久瘁锋镝，即令罢兵还其疆域，反其旄倪。高丽君臣感戴来朝，义虽君臣，欢若父子。计王之君臣亦已知之。高丽，朕之东藩
也。日本密迩高丽，开国以来，亦时通中国，至于朕躬，而无一乘之使以通和好。尚恐王国知之未审，故特遣使持书，布告朕志，冀自今以往，通问结好，以相亲睦。且圣人以四海为家，不相通好，岂一家之理哉。以至用兵，夫孰所好，王其图之。[1]
翻译成现代文之后的大概意思是：
自古以来，小国之君尚且追求与邻邦和睦相处、互通往来，更何况朕！朕的祖宗承受天命，现在是整个华夏的主人，无数国家已经臣服。朕刚即位的时候，看到高丽百姓遭遇战争之苦，所以就命令停止战争，退还他们的疆土，释放了俘获的俘虏。高丽君臣感恩戴德来朝，现在名义上是君臣，实际上相处很愉快，就像父子之间一样。估计您的臣子们都知道这些事。
高丽是朕在东面的属国，而日本靠近高丽。自日本开国以来，一直与中国通好，可到了朕这一代，却没有派过一个使臣来通好。因为担心你们对这些情况不太了解，特派使臣持朕的书信转达心意，希望从今往后，两国互通往来、好好相处。圣人认为四海都是一家人，我们不互相通好，难道是一家人的道理吗？至于兵戎相见，有谁喜欢呢？大王认真考虑一下吧。
这封书信的字里行间透露了忽必烈的不快：你们日本自开国以来，便与中国往来甚密，在汉唐之时还经常纳贡，而我蒙古帝国承天授命，开疆拓土更甚前朝，你们反而不过来朝觐，这不是瞧不起朕吗？！
这位大汗要表达的意思很清楚：
[1]《元史》卷六，《世祖本纪三》。
如果日本向元朝称臣，元朝会像对待高丽一样，与日本国愉快地相处，就像父子之间一样；如果日本不向元朝称臣，元朝必然起兵讨伐之，届时，日本人所遭遇的痛苦，就像之前反抗的高丽人一样。
两位出使日本的侍郎先取道高丽。在那里，高丽国王王禃已经挑选好了向导：枢密院副使宋君斐，以及借礼部侍郎金赞等人。在这些向导的帮助之下，殷弘、黑的等一行人前往日本。按照《元史》的记载，这次出访的结果是“不至而还”，也就是说，没有到达目的地就回国了。[1]
在呈给忽必烈的奏折中，宋君斐解释了“不至而还”的原因：“（黑的一行人等）至巨济县，遥望对马岛，见大洋万里，风涛蹴天，意谓危险，若此，安可奉上国使臣冒险轻进？！”[2]意思是说，大海风高浪急，不敢让蒙古使臣冒险轻进，所以才放弃了出使日本。
但是，在蒙古大汗忽必烈看来，这次出访之所以“不至而还”，是因为高丽人没有尽力。于是，在公元1267年6月，又派黑的、殷弘等去高丽，诏谕王禃通使日本事宜，说是“以必得要领为期”。但王禃认为海道多有险阻，不能让蒙古特使受委屈。于是，在9月派其起居舍人潘阜等持忽必烈书信前往日本。《元史》写道，潘阜等人在日本逗留了6个月，“亦不得其要领而归”。
但《元史》的记录似乎不完整。据日本东京大学历史学家石井进考证，潘阜等人抵达了九州岛，并进入了太宰府——九州的管理机构，还将书信转交给了太宰府官吏，时间是在1268年1月。不过，在作进一步介绍之前，有必要先交代一下蒙古与高丽的关系。
[1]《元史》卷二百○八，《外夷列传一》。
[2]郑麟趾：《高丽史》卷二十六，《世家》第二十六。