After its landslide victory in the Lower House elections of August 2009, the Democratic Party of Japan strove for change in Japan’s foreign and security policies. Newly elected Prime Minister Yukio Hatoyama challenged the way the forward deployment of US military to Japan was being put into practice in Japan. This political conflict was symbolized in the stalling process of relocating the US Marines Corps Air Station of Futenma, which is located in Ginowan city, one of Okinawa Prefecture’s most densely populated areas. Hatoyama vowed to work for a relocation of the Futenma units to a place outside of Okinawa Prefecture, while the US-side insisted on carrying out the relocation plan to Henoko, District of Nago in Okinawa, which was agreed upon in 2006 with the previous administration under the leadership of the Liberal Democratic Party of Japan. This paper investigates Hatoyama’s negotiation efforts on the future of Futenma with the Obama administration on the one hand and with the local politicians and citizens of Okinawa on the other hand. The paper is a qualitative study following the concept of Two-Level Games. It will be argued that Okinawa became the symbol of the Hatoyama administration’s struggle (and failure) to implement Japan’s new foreign and security policy as an equal partner in the alliance with the US.