20世紀70年代初期，已在台灣、香港、東南亞各國華人社會中擁有巨星地位的鄧麗君，開始接受新的挑戰。
當時的日本是亞洲最大的流行音樂市場，多少歌手抱著從此登上國際舞台的玫瑰之夢來到了這個繁華的島國，可是又有多少人在經歷了嚴酷的競爭後不得不默然離去。當時在亞洲的音樂中心——日本歌壇走紅的華人歌星屈指可數，能得到日本認可的僅有翁倩玉、歐陽菲菲和陳美齡。其中翁倩玉、歐陽菲菲是鄧麗君的前輩。在日本出生、成長的翁倩玉最先成名，她隨父旅居日本，雖未入日本籍，但受成長環境的影響，已算是半個日本人了。隨後來自台灣的動感歌星歐陽菲菲走紅日本，後來就嫁作日本媳婦，與日本也有淵源。與鄧麗君同期出道、來自香港的陳美齡，以當時日本流行的青春偶像路線走紅，她算是第一位以華人身份成功打入日本歌壇的女星。鄧麗君雖是負著台灣、香港、東南亞的盛名而來，但進入日本這一陌生的地域，一切還得從頭再來。
當時由德國人投資的日本寶麗多公司（Polydor）對亞洲的流行音樂保持高度敏感，其德籍董事希望將亞洲實力派歌星推上日本舞台，這是鑒於容貌清純可愛、歌聲甜蜜動人的陳美齡及以前的翁倩玉、歐陽菲菲在日本走紅的激勵，這位董事一直想再找一位偶像。1973年，歐陽菲菲和陳美齡雙雙在日本拿下唱片大獎，引起不少日本唱片公司對華人歌手的興趣。日本寶麗多唱片派出星探，尋求偶像型華人歌手。三個月後，製作部的工作人員在了解董事的想法後立刻放眼香港，希望能找到兼具實力與魅力的歌星。他們先是試聽香港寶麗多推薦的歌手的試音帶，參觀他們的舞台表演，展開了一系列尋訪活動。
為了尋找偶像歌星，寶麗多公司於1973年派員到香港的大小歌廳、夜總會尋覓。派去的兩位星探，訪遍全港九，終於在東方歌劇院發現了一張清純的面孔，這正是他們所要找的那種具有青春氣息的少女歌手。於是，他們便馬上跟寶麗多在香港的負責人鄭東海聯繫，一起去拜訪這個女孩。這個剛滿20歲的鄧麗君，她清新的外形和甜美的歌聲立即讓星探們打道回日本，報告好消息。
寶麗多製作部經理，也就是後來任金牛宮唱片公司總經理的舟木稔立刻飛到台北，來說服鄧麗君及其家人跟他簽約。
儘管港台樂壇出現了令人驚喜的一幕，但國語歌在形式上依舊沒有突破。各類夜總會、酒吧和俱樂部的興起曾經帶動了音樂的發展，但隨之而來無不是以太平盛世、浪子心聲、酒廊怨曲等為絕對主題的音樂，尤其是台灣流行音樂正逐漸失去了對人們的吸引力。一些年輕的歌迷在厭倦了日式哭調發展來的台語歌和舊上海式的燈紅酒綠後，轉而便在西洋音樂中釋放各自的情感。此外，唱片業、版權法的不健全，也使得台灣歌手紛紛尋求海外發展。留在本土的鄧麗君、青山、姚蘇蓉等也不得不頻頻到香港等地演出。
鄧麗君也隱隱感到了一種危機感，在舞台上唱的歌曲越來越定型化，沒有新的歌路可繼、沒有新的唱腔可用。在疲憊勞頓的一場又一場的演出之後，鄧麗君也有些倦怠，隨著觀眾的要求和品味越來越高，演出時的掌聲也沒有16歲那年初到香港時那麼熱烈了。無論如何，需要推陳出新。雖然自己出道早是一種優勢，但同時也是一種缺陷，根基太淺了，很容易曇花一現。鄧麗君得到的那些零星的歌唱訓練畢竟不能與正規系統的訓練相比，雖然她有絕好的天賦。但長此以往呢？
寶麗多的出現無疑是一個重要的機遇，既可以走上國際歌壇之路，又可以接受長期的正規系統的音樂教育。於是，鄧麗君和鄧媽媽親赴日本考察了一番後，鄧麗君才決定和寶麗多簽下了五年的契約。
寶麗多製作部經理舟木稔憶及當時簽約時說：「她自己躍躍欲試，不過她父親卻不贊成。我請他放心，告訴他我們的方針與計畫，並且說明了一下日本樂界的情況，不過事情還是沒有結論。她父親認為既然在台灣與香港已走紅，就不必在日本從頭開始。」
鄧麗君曾表示，之所以到日本發展，是自覺在東南亞的歌唱事業已達到高峰，想另闢戰場。「其實，我並不喜歡生活在異鄉。但是，日本完善的歌唱條件和環境，難找的好樂隊，能夠使我在每一次大型演唱會之後，針對自己的缺點與不足，不斷改進，精益求精。」鄧麗君的弟弟鄧長禧也說，鄧麗君到日本發展完全在計畫之外，因為這等於要暫時放下東南亞市場，但在唱片公司主動與她聯繫後，她對這突如其來的邀約仔細考慮了一陣子，認為日本市場更大，才毅然赴日。
對於鄧麗君赴日發展，她的老師姚厚笙說：「日本音樂界當時比台灣進步許多，所以我覺得是個很好的學習機會。台灣的樂隊只有簡單的吉他、鼓、鍵盤等樂器，日本卻有大型的樂團，樂器種類繁多。
光這點，音樂就豐富許多。唱歌時有時候還有管弦樂團伴奏。她的聲音之所以更奔放，唱歌的感情之所以更豐富，可能就是這個緣故。」
香港RTHK的製作人張文新則是如此看待她進軍日本的結果：「我覺得她唱歌的技巧進步許多，在日本可能吃了不少苦，不過現在終於看到成果了。她可以唱得非常有感情。還有一點就是她可以說是以國語介紹日本歌曲的文化交流者。日本的曲風、感性與傳統的中國式唱法已在她的體內合而為一。這在香港而言是一種全新的感受。」
當時台灣方面對鄧麗君進軍日本，多少有點不滿，不過隨著她在日本闖出名氣，也就以她為榮了。
1973年，鄧麗君以「香港最受歡迎的歌手」身份踏上了日本的國土。在一個女性周刊的策划下，她從羽田機場直赴日本歌手森進一舉行的聚會。在聚會上，鄧麗君獻上了幼時常唱的歌曲《愛你入骨》。
她那婉轉清脆的歌聲，一下子讓日本人喜歡上了這個明媚的女孩。
當然，這並不意味著鄧麗君的歌曲就被嚴格的日本音樂界所接受。初到日本，鄧麗君到寶麗多公司面試時很不順利。那一天，在寶麗多公司總部電視塔（NHK） 的錄音大樓里，鄧麗君錄製的是她十分熟悉的歌曲《無論今宵或明宵》，但在這個陌生的國土上，在寶麗多現代化的錄音廳里，在這個大牌公司權威人士的注視下，一向從從容容、歌喉清亮、吟唱自如的鄧麗君卻臨場發揮得很不好。也許是因為她向往日本，羨慕像寶麗多這樣的名牌唱片公司，使她精神壓力太大了。錄製的唱片更不盡如人意，錄了三遍才錄成。折騰了幾個小時，錄製的歌曲當眾播放出來的時候，錄音廳內所有前來觀看的公司董事們都大失所望，嘆息連連。他們交頭接耳、議論紛紛，有的連連搖頭，不以為然，有的心灰意冷，已經離座。這位就是他們訪遍港九、不惜重金請來的歌壇新秀？如此的實力怎麼在歌壇立足呢？
鄧麗君急得一時不知如何是好。正在這時，在一旁觀看的渡邊娛樂公司的總經理渡邊正一卻看到了鄧麗君的潛質。渡邊娛樂公司與寶麗多唱片公司頗有淵源，但卻並不隸屬與寶麗多，不過渡邊娛樂公司正一欠寶麗多一個很大的人情。基於鄧麗君的可造之材以及還寶麗多人情，渡邊正一力排眾議，將鄧麗君接到了自己的公司，並安排她學習日語，接受正規系統的音樂訓練。
1973年，鄧麗君正式與日本渡邊娛樂公司簽約，並與寶麗多合作發行唱片，赴日接受密集訓練。
鄧麗君在日本完全是一個新人，於是渡邊娛樂公司努力從各方面來全力打造她，從訓練、宣傳、灌唱片、上電視到登台演唱、巡迴演出。他們還針對鄧麗君的歌路，專門為她譜寫新歌，有專門的作詞家和作曲家為鄧麗君服務。作詞家荒木豐久、作曲家三木剛幾乎寫了鄧麗君在日本所有最受歡迎的歌曲。
這種專業化和專門化的訓練，收效甚好。在渡邊娛樂公司和寶麗多的密集培植和力捧之下，鄧麗君完全變成了一個成熟的歌星，為邁向「國際巨星」打下了堅實的基礎。
為了能在日本立足，鄧麗君必須演唱日文歌曲。她雖然確立了國語歌星的地位，但現在卻是以華人歌手的身份闖進日本市場，這對鄧麗君來說是一次極大的冒險。
未到日本前，鄧麗君對日語可以說是一竅不通，簽約後，渡邊娛樂公司才安排她學習日語。公司為她請來的是日籍華僑，可是華僑雖然日語流利，國語卻忘得差不多了。兩個人講起話來，還得比手劃腳。結果，鄧麗君還得自己多加努力，從字母學起，不到一年的時間，她就能說會寫了。她曾經笑稱，她最先學會的日語好些是「粗話」，但一句話也不敢說，只能備而不用。
據一位著名的音樂評家說，鄧麗君學習語言的能力是相當驚人，比如她第一次前往香港發展，剛開始還不會說粵語，第二天就會說幾句，第三天就能以粵語在電視上與主持人簡單交談，同時在夜總會也能演唱粵語時代曲。這種表現和能力自然很快就打開了當地樂迷的心扉。其他的語言如日語、英語、法語，只要給她一段時間，鄧麗君就能準確使用而