忽必烈向高丽人提出的或许是最苛烦的要求， 是协助他与日本建立联系。 在长达四个世纪的历史时期内， 日本岛国的大部分地区在很大程度上处于与中国完全隔绝的状态。 由于9世纪中叶佛教在中国遭受迫害， 日本与中国逐渐疏离， 直至最后决定几乎完全切断与中国的贸易和文化联系。 对于忽必烈来说， 如果能与日本重建朝贡关系， 就能在汉人心目中树立自己的高大形象， 这将是其他任何方法都无法比拟的。 正是这种急于博取汉人赞赏的心态， 促使他决定一定要与这个日出之国建立联系。 但直到那时为止， 蒙古将领还从未参加过海战。 而此时忽必烈做出了一个重大的决定， 要跨海降伏这个岛国。 虽然他并没有打算发起一场海战， 但是他降伏日本的计划最终导致了悲惨的结局。
高丽人不喜欢日本人， 但是他们并不热衷在忽必烈控制日本的计划中担当中介的角色。 自从1223年以来， 高丽沿海地区就一直遭受着被称为“倭寇”的日本海盗的袭击和抢掠。 日本海盗利用高丽遭受蒙古入侵而无暇防备的机会， 大肆侵扰高丽的沿海地区， 直至1263年。 但是高丽王室认识到， 日本海盗的行为并不是由日本政府或者日本军事政权支持或认可的， 因而没有对日本宣战。 它仅仅派遣使者抗议日本海盗的袭击。 一旦日本海盗获悉蒙古人已经征服了高丽， 而朝鲜半岛战事已消除， 他们便停止了袭击。 因此， 高丽人并无特别的兴趣帮助蒙古人与日本建立联系。
然而， 忽必烈另有想法。 在1266年的秋天， 他派遣使节向日本人通报了新朝在中国建立的消息， 并请他们向新皇帝进贡。 高丽人负责帮助使团横渡海峡。 负责接待忽必烈使团的高丽人试图劝阻他们执行使命， 并警告他们说， 日本列岛附近的海面风急浪高， 气候恶劣， 异常危险。 事实上， 高丽人根本不想被卷入蒙古和日本的关系之中。 高丽人的恫吓终于奏效， 蒙古使者对充满危险的赴日旅程感到气馁， 于是匆匆返回中国。 他们的报告激怒了忽必烈， 他也认为高丽人不值得信赖。 在1267年的夏天， 他给高丽王廷写了一封措词严厉的信， 斥责他的“属民”不仅不协助他的使节， 反而阻挠他们前往日本。 他决心排除高丽人的干扰， 再做尝试。
1268年， 他再次派遣使团前往日本， 这一次高丽人比较合作。 特使中包括一位礼部官员和一位兵部官员。 忽必烈指示他们向日本人通告他已经登基的消息， 并向他们表明， 日本应该向他称臣纳贡。
日本人并不欢迎蒙古使团， 他们的行动正好为在政策上一意孤行的忽必烈提供了进攻日本的借口。 位于京都的日本皇室实际上非常软弱无力， 真正的权力掌握在镰仓幕府手中。 幕府里， 幕府执权北条时宗是最终的决策者， 而他并不打算顺服蒙古。 自恃拥有骁勇善战的武士阶层， 凭借偏居大洋、 易守难攻的日本列岛， 他和他的前任执权北条政村一样， 断然拒绝了蒙古使者的建议。 忽必烈在信函中曾提到日本天皇是一个“小国国君”。 在初步讨论了应该如何回复忽必烈这封信之后， 幕府决定干脆直接把蒙古使者遣送回国， 连只言片语也不回复。 虽然朝廷官员已经起草了一封和解信并抄寄了一份给幕府请求批准， 但幕府执权没有批准寄出公函。 忽必烈并不为日本政府的反应所动， 在1271年初再次派遣使团带着同样的信息赴日。 负责护送蒙古使节的高丽人秘密地警告日本人， 他们将面临蒙古人的军事威胁。 可是日本人再次拒绝蒙古使节进入王廷。 在返国途中， 蒙古使节抓住了两个日本渔民， 把他们带回中国。 忽必烈热情款待了日本渔民， 命令他们请求他们的统治者对中国皇帝和蒙古大汗表示适当的尊敬， 尽快派遣使者前来进贡。 然后他派人护送他们经高丽返国。 可是， 日本方面对忽必烈释放被扣留的日本渔民没有任何反应。