在海都的叛意逐漸明朗的時候，忽必烈注意到大海彼岸的一個獨立國家日本。日本與西方各國以及南宋完全不同。
西方各國和南宋同蒙古是接壤的，日本雖然曾經通過僧侶和商人與中國有著頻繁的往來，但是正式的國交已經在八九四年日本廢止遣唐使以來，斷絕了四百多年。忽必烈得到的關於日本的信息，不過是僧侶、商人和漂流民等帶來的片段。
忽必烈對日本這個國家很憧憬，而且，遠征日本也符合「天涯海角」的志向。
當時，有幾個日本商人因海難漂流到高麗，被高麗國王王（亻典）的使者帶到了大都。忽必烈親自會見了這幾個日本人，詳細詢問了日本的情況。
據他們說，日本擁有先進的文化，神聖的天皇在京都，武士掌握政權，盤踞鎌倉，發號施令。忽必烈對他們所說很感興趣，同時也下定決心征服日本。
在對南宋作戰的時候，忽必烈便就此徵求大家的意見，但是大多數人對遠征日本持反對意見。
「日本與我們之前的敵人不同，我們原來的敵人都是陸地相接的，而日本卻在海上。而且，我們得到的有關日本的一切，不過是從高麗人和商人們那裡得到的一些片面信息。最近海都有叛心，隨時可能起兵反叛。在這種時候分散兵力發起遠征，是非常危險的。」伯顏首先提出反對。
伯顏是忽必烈帷幄之中第一人，任中書左丞相。他是八鄰部闊闊出的兒子，青年時代在波斯度過，頗有見識。
右丞相安童也支持伯顏。大部分人都反對，忽必烈不能不顧大家的意見，強行發起遠征，便道：「你們說得很對。朕不是說要立即發起遠征，眹想先派出使者，命其來朝貢。如果對方拒絕，我們再派出遠征軍。日本看到帝國的軍威，必然會屈服。南宋已經是囊中之物，將來攻打南宋的時候，再派些船，一舉征服日本。」
忽必烈如此輕描淡寫，眾人不好再說什麼。
一二六六年，忽必烈第一次嘗試與日本接觸。當時，高麗在蒙古的幫助下，消滅新羅，建立了高麗王國，成為蒙古的忠實附屬國。
由於日本的信息缺乏，於是忽必烈委託與日本相近的高麗與日本接觸。
當時的高麗國王元宗非常為難。奉蒙古的命令與日本接觸，成功倒沒什麼問題，萬一失敗，說不定會惹怒忽必烈，高麗自身難保。而且，自視甚高的日本不可能接受忽必烈提出的朝貢條件。高麗的重臣李藏用明白元宗的心思，說道：「我們不如答應忽必烈的要求，帶蒙古的使者前去。到中途，再以風濤險阻和海路危險為由撤回，這樣既能保住我國的體面，又能不讓忽必烈生氣。蒙古的使者不習水性，只要選擇風浪較大的日子開船，使者必然會因為害怕而折回。」
元宗聽了這個建議，大喜。一二六六年，高麗的官員將蒙古的兵部侍郎黑的和禮部侍郎殷弘帶到慶尚南道的巨濟島，正好碰上天氣不好，海浪很大，二人因為害怕撤回。一切都如李藏用所料。
黑的和殷弘歸國之後，將元宗的話轉達給了忽必烈，說高麗與日本幾乎沒有聯繫，海路非常危險，請求結束與日本的交涉。
忽必烈聽了二人的話，嗤笑道：「元宗這傢伙，是害怕交涉失敗才以風濤險阻為由的。這樣更好，以後對日本的交涉，就全部交給高麗，把這些話轉告給元宗。」
忽必烈幫助高麗取得了半島霸權，並非無償。蒙古人第一次侵入高麗，從一個叫趙彝的俘虜口中得知日本的繁榮後，就已經野心勃勃。
如果真如趙彝所說，則日本將是不可小覷的敵人。當時，忽必烈害怕的是宋與日本聯手。在征服宋之前，必須設法牽制日本。忽必烈想利用高麗來牽制日本。元宗勸忽必烈停止對日交涉，正中忽必烈下懷。
忽必烈對元宗下令：「今有爾國人趙彝來告。日本與爾國乃是近鄰，典章、政治皆有可嘉，自漢唐以來，或遣使通中國。朕以卿負責此事，勿以風濤險阻為由而辭，勿以此前與日本無通好關係而拒。卿之忠誠，可見於此，卿自勉之。」
忽必烈就這樣將對日本的交涉全權交給了高麗。
第二年，高麗使者潘阜帶著忽必烈的國書和元宗的書信渡海。十一月到達對馬，一二六八年一月，到達太宰府，將忽必烈的國書和元宗的書信呈遞給鎮西奉行少二覺惠資能。
資能看後大驚，忙轉交鎌倉幕府。此時鎌倉的執政是元老北條政村。北條氏的嫡系時宗還是一個十八歲的青年，位至聯署（執政的輔佐職位）。北條時宗三月五日才就任幕府的第八代執政。在他的父親——前代執政去世的時候，由於時宗年幼，當時的聯署政村便繼任執政，準備等時宗長大成人，再將權力還給他。
蒙古的國書內容大致如下：
「大蒙古國皇帝奉書日本國王：朕惟自古小國之君，境土相接，尚務講佶修睦。況我祖宗，受天明命，奄有區夏，遐方異域，畏威懷德者，不可悉數。朕即位之初，以高麗無辜之民久瘁鋒鏑，即令罷兵還其疆域，反其旄倪。高麗君臣感戴來朝，義雖君臣，歡若父子。計王之君臣亦已知之。高麗，朕之東潘也。日本密邇高麗，開國以來，亦時通中國，至於朕躬，而無一乘之使以通和好。尚恐王國知之未審，故特遣使持書，布告朕志，冀自今以往，通問結好，以相親睦。亂聖人以四海為家，不相通好，豈一家之理哉。以至用兵，夫孰所好，王其圖之不宣。」
總之，這封國書的意思是說：忽必烈依照天意，就任天賜的大國皇帝。即位之初，看到高麗的百姓受苦受難，於是派兵前去拯救，現在高麗已成為帝國的東藩，與帝國相交甚好。而日本與高麗相鄰，也常與中原通好，為什麼不派使節來見朕？如果日本拒絕通好，將會違背聖人所說的四海一家的道理，忽必烈將不得已派兵以武力征服。
總之，表面上看是要求通好和睦，實際上卻是戰爭宣言。
鎌倉幕府的人讀完忽必烈的國書之後，吃驚的同時也非常憤怒。
日本自源平之爭以來，名義上的政權在京都（朝廷），而實際上的實權卻掌握在鎌倉幕府的手中。但是，在此之前，戰爭都是內亂，從來沒有受到過來自外國的侮辱和挑釁。
而且，日本在律令體制下，以唐為鄰國，自推古朝派遣遣隋使以來，―向與中國採取對等的外交。而至於朝鮮半島，自神功皇后以來，一直將其視為自己的朝貢國。
唐亡宋興，新羅滅，高麗興，這些都沒有改變日本對中、朝的認識。
然而，朝鮮不知何時被北方勃興的蒙古征服，忽必烈自稱為神聖帝國的皇帝，現在來要求日本臣服。
這個時期，日本的排外思想增強，以朝廷為中心並以信奉神靈保佑的神國思想為基礎的國家觀念也增強了。忽必烈的國書否定了日本的神性，奪走了歷史上的朝貢國，並要求日本臣服，日本不可能答應這樣的要求。
當時剛滿十八歲、血氣方剛的時宗怒道：「北方的蠻夷竟稱我萬乘之君為小國之君，欺人太甚。說什麼受天明命，簡直是不知天高地厚。立即斬掉來使，以宣我國威。」
時宗雖然已經怒不可遏，似是此時的他其實也已經聽說蒙古帝國的廣袤版圖和強大的軍事實力。
執政北條政村已經六十三歲，雖然權勢日衰，值是作為支撐著鎌倉幕府的老臣，一向行事謹慎。
「國書以大蒙古國皇帝奉書日本國王開始，以不宣結束，就說明在今後的交涉中並不要求日本臣服。還有，所謂不好用兵這句話，雖然是恫嚇，但是與之前蒙古的強硬姿態不同，這是承認日本可以以一個不臣服的朝貢國與其通好。這是建國以來的大事，不能只由幕府決定，應該奏明朝廷。」政村制止了衝動的時宗。
幕府中的人大都贊成政村的建議，對蒙古國書的回覆一事則交給了朝廷。
掌握著武家政權的幕府選擇了逃避，而將這個燙手的山芋扔給了朝廷。朝廷接到國書之後，上上下下陷入了混亂，當時在位的天皇是龜山天皇，後嵯峨天皇作為太上皇，實施院政。
這一年，後嵯哦天皇正準備慶祝五十歲的壽辰，接到幕府的奏請之後，立即中止了壽辰的準備活動，在太上皇的住所召集重臣，連日舉行會議。
左大臣近衛基平與鎌倉的時宗一樣，態度強硬，堅持主張立即拒絕蒙古的要求。但是由於意見不一，會議並未作出決定。
這是事關國家命運的大事。蒙古使者到達日本的消息很快傳遍全國，引起了軒然大波。近衛基平在他的日記《深心院關白記》中寫道：「國家珍事，大事也，萬人驚嘆而無他。」
結果直到二月，京都朝廷才做出不予回答的決定。
三月，鎌倉的時宗繼任執政，政村改任聯署。
在當時的日本，京都的朝廷、幕府的將軍和執政共同治天下，但是實際權力（兵權）卻掌握在幕府的執政手中。一二六六年七月四日，第六代將軍宗尊親王（後嗟峨天皇之子）因被疑謀反而被剝奪將軍職，送還京都。那之