1964年（昭和三十九年）11月，佐藤內閣成立。
除了官房長官換成了橋本登美三郎外，其他的內閣成員完全沿用池田內閣的原班人馬。這種無縫對接的政權交替，讓佐藤可以順利地展開工作。
佐藤上任後的第一項工作，就是確定了1965年訪問美國。佐藤是個大膽的人，他在訪美期間，把一個超級敏感的問題拋了出來，那就是讓美國人返還衝繩島！
佐藤榮作後來在自己的回憶錄中說道，他讓約翰遜總統第一次認識到美國在琉球和小笠原群島上的軍事設施對遠東安全極為重要。
佐藤榮作在會談中明確提出，希望美國儘快將這些島嶼的政權歸還日本。約翰遜沒有想到日本首相敢於提出這樣“無禮”的要求，只能支支吾吾的對應著，說對日本提出這樣的想法表示理解，並且期待著遠東自由世界的安全保障形勢。
這是什麼？這就是太極拳裡德推手！
約翰遜告訴你，這事我沒說不答應，可以談，但是日本人你也要知道，沒有美國的駐軍，你們的安全將無法保障。這就是給足了佐藤榮作面子，又做出強勢的姿態。
美國人對沖繩問題不肯讓步，有他們自己的考慮，因為在1965年2月，越南戰爭正式爆發了，美軍每天都要派出大量的轟炸機對越南進行轟炸，但是聚集在遠東的航母平臺遠遠不能滿足這個需要，所以沖繩美軍基地就變得越來越重要了。
很多人當時並不明白，一向做事謹慎的佐藤榮作，為什麼會突然拋出一個如此唐突的外交炸彈呢？
其實，這才是佐藤榮作真正高明的地方。因為他知道日本不可能在短期內要回沖繩的主權，但是對於美國人來說，沖繩是個巨大的魚餌，吃掉它，就必然要承擔更多的責任，甚至要對日本展開更多的金錢上的幫助。
對返還衝繩的態度越消極，說明美國人“吃人嘴短，拿人手短”的心態越嚴重，而美國人也在這段時間內放開了對沖繩島居民的管制統治，而是在管理上放給了他們高度的自治權，讓當地居民的生活水平大大提高，並且在以循序漸進的方式實現沖繩與本土的一體化。
美國人的目的很明確，他們無意把沖繩變成美國的領土或殖民地，他們只需要這裡作為他們的軍事基地，對遠東可以隨時展開軍事打擊的巨大戰爭平臺。
而後來，人們漸漸發現，佐藤榮作之所以是個偉大的政治家，是因為他可以持之以恆且毫不懈怠的實現他的目標。
對於沖繩島，他要的不只是美國的放松管制，他要的是主權。
既然，約翰遜並沒有用當年的艾森豪威爾一樣，用強硬的口氣拒絕歸還衝繩。就說明他已經咬上了魚餌，而作為一名優秀釣手來說，佐藤榮作怎能放棄這樣的機會，他想在自己的任期內完成收復沖繩主權的偉業。
佐藤榮作在回國後，立即發表演說：“沖繩被從本土分割出去已經二十年了，我們一刻都沒有忘記九十萬沖繩同胞。我深深地知道，只要沖繩不迴歸祖國，對我來說戰後佔領時代就沒有結束。”
這段演說非常著名，在日本各大報紙頭條刊登後，立即輿論譁然，很多人都在認為佐藤榮作在說大話，為保住自己的政治地位增加更多的砝碼。甚至連解決該問題的外務省都在半信半疑佐藤的決心，他們都認為想讓美國人把沖繩島吐出來，那是一件比登天還難的事。
那麼，給佐藤信心的事情是什麼呢？其實是中國大陸發生的重大變化。
要知道，中國大陸當時已經和蘇聯交惡，冷戰格局被徹底打亂。來自中國大陸的威脅，已經減輕了許多。那麼沖繩島在越戰後是否還具有它本身的戰略價值，就是值得美國人考慮的事情了，佐藤早已看到了這一步。
1967年11月，佐藤、約翰遜舉行了第二次會談，決定首先歸還小笠原諸島，並在共同聲明中寫入希望在三年內歸還衝繩時間要達成一致。雙方交涉的焦點就在於美國提出的返回沖繩島主權後，如何不對沖繩的“遠東和平與穩定所發揮的作用”造成損害，即返還後，美軍基地是否還能存在的問題？
佐藤針對這個問題，成立一個特別的部門叫“基地問題研究會”，當然這個研究會對外是完全保密的，甚至連當年的外交局都不知道它的存在。最後研究會拿出了他們的研究成果，他們認為沖繩基地有兩個問題是無法繞開的，第一就是撤走部署在沖繩的戰術核武器問題，第二是確保美軍自由使用基地，包含運入核武器的問題。
隨後，日美雙方關於沖繩島問題的進行了一系列秘密的磋商，京都產業大學的若泉敬赴美，與約翰遜政權的特別助理羅斯特、尼克松政權國家安全顧問基辛格進行接觸，收集信息，並在私下進行折中的談判。
佐藤並沒有採用政府官員充當特使，而是用學院派去秘密訪美，這樣的方式既可以掩人耳目，也可以降低美國方面的防備。至此，外界對佐藤如何討還衝繩島，還一無所知。佐藤也沒在任何場合透露過他的真實想法，所以外界對他的意圖一無所知。
佐藤永遠是個讓人琢磨不透的人，就在短暫的沉寂過後，1961年1月，他突然對美國提出了撤走沖繩島上的核武器，要求美國無條件適用《日美安保條約》和包括禁止核武器運入的無核三原則，他要求美國駐日大使盡快給予日方答覆。
這個方案來得太突然了，就連日本內閣官房長官都覺得半信半疑，他真的不相信佐藤有這樣的決心去跟美國人叫板。兩個月後，佐藤在參院預算委員會回答社會黨議員前川旦的質詢時明確表示要以“撤走核武器”作為歸還方針，這是他首次在國會明確表達了自己在這個問題上的主張。
很多人當時都在猜測，佐藤能夠做出這樣高調姿態的底氣來自哪裡？事實上，當時美國的核武器戰略發生了巨大的變化。由於可搭核武器的核潛艇的出現和核運送技術的發展，在沖繩經常性部署核武器的必要性在減弱。
當然，此時阻礙沖繩島返還的越戰因素也在漸漸緩和，由於美國深陷越戰泥潭，美軍在雨林中的作戰越來越困難，越南的軍隊在密林中神出鬼沒，大量的傷亡讓美國人第一次在海外戰場感到了絕望。1968年4月1日，美國總統約翰遜在演說中表示部分停止對北越的轟炸，呼籲河內開始和平對話，這說明一向嘴硬的美國人已經撐不住了，不斷增加的陣亡者和經濟負擔導致了國民批判政權的運動擴大到了全美國。
1968年11月，尼克松接替了約翰遜成為了美國新任總統，幾乎是同時，自民黨的總裁大選也開始了。
毋庸置疑，這次總裁選舉中各個候選人對沖繩問題的態度，成為了競選的焦點。辭去外相參選的三木武吉在競選中明確提出了自己對沖繩問題的態度：“沖繩返還時，在沖繩的美軍基地應和本土的美軍基地一樣適用無核三原則。”另一個候選人前尾繁三郎也提出了同樣的主張。
但是，這些競選言論不過是為佐藤榮作的當選，做個適當的點綴罷了，因為這個主張佐藤榮作很早就提出來過，用這樣的主張做競選言論，毫無新意。11月，佐藤榮作順利地第三次當選自民黨總裁。
美國方面此時也終於開始在官方的言語中對沖繩島問題有了明確的態度，首先他們承認如果沒有沖繩縣日本人民的支持，美國的軍事基地就不可能穩定、順利地運營。
面對美國這樣的表態，佐藤已經將拳頭握緊，準備發動沖繩島主權歸還談判的最後一擊，他的態度很明朗，沖繩島必須即時、無條件、全面歸還。
日美雙方最後的談判展開了，在尼克松和佐藤雙雙當選後，兩個人便舉行了第一次正式會晤，美國隊歸還日本沖繩島主權並無異議，但是雙方最大的爭議焦點是美國是否可以在緊急時刻再次運入核武器自由使用的問題。
要知道，日本是世界上迄今為止，唯一一個受到過核打擊的國家，對於核武器的恐懼，他們比任何人都敏感。所以，對這個問題，佐藤榮作表示為難。
尼克松之後又做出了讓步，提出了“應該在不損害美國政府在《日美安保條約》中關於事先協商制度的立場，並向首相確認了實施沖繩返還不與日本政府的政策背道而馳。”這是一個大套的文字遊戲，主旨就在於核武器這三字，並沒有出現在這份聲明中。
出了緊急情況雙方商量著辦，也就是說關於核武器的使用上，佐藤榮作給美國留了一個口子，美軍在緊急情況下仍可以使用沖繩基地，包括運入核武器，但這事心照不宣，不能體現在聯合聲明中。
就這樣，沖繩島迴歸的一切障礙都已經掃清了，1972年5月15日，沖繩最終迴歸到了日本的懷抱。
沖繩島的迴歸，是佐藤榮作一生中最精彩的一個華章，它凝聚了佐藤高超的政治智慧和外交能力，堅韌的性格和強硬的手腕。佐藤榮作能夠根據對象不同，而改變政治策略。他的政治上的成功值得每一個當代或者是未來的政治家們去思考。
《夜狼文史工作室》特約撰稿人：大鬍子二零
