5 月 23 日 、 首相 の 鳩山 由紀夫 は 沖縄 を 訪問 し て 知事 の 仲井 眞 弘 多 と 会談 し 、 自公 政権 時代 に 合意 し た 辺野古 移設 で 米国 政府 と 合意 文書 を 交わす 方針 を 説明 し た 。

仲井 眞 は 辺野古 移設 の 方針 について 「 大変 遺憾 」 「 極めて 厳しい 」 と 述べ た 。

5 月 28 日 、 日 米 両 政府 は 米 軍 普天間 飛行場 移設 に関する 共同 声明 を 発表 し 、 移設 先 を 名護 市 の キャンプシュワブ 辺野古崎 地区 と これ に 隣接 する 水域 と し た 。

後継 首相 と なっ た 菅 直人 は 「 普天間 基地 の 移設 ・ 返還 と 一部 海兵 隊 の グアム 移転 は 、 何 と し て も 実現 し なけれ ば なら ない 。

2009 年 から 2010 年 5 月 まで に 政府 や 地元 自治体 、 社民党 ・ 国民 新党 が 提案 し た 移設 先 は 、 辺野古 陸上 ・ 勝連 半島 沖 ・ 嘉手納 飛行場 ・ 大村 航空 基地 ・ 鹿屋 航空 基地 ・ 徳之島 ・ 馬毛島 ・ 硫黄 島 ・ グアム 島 （ 既に 移転 計画 が ある もの を 全面 移転 に 拡大 する ） ・ テニアン 島 （ 地元 が 移転 を 容認 し た ） など が ある が 、 いずれ の 案 も 正式 な 計画 として 合意 さ れ なかっ た 。

『 読売新聞 』 に よれ ば 、 アメリカ 政府 側 は 、 日本 政府 が 提示 し た 様々 な 「 移設 案 」 に対し 「 新た な 案 の 詳細 や 実現 可能 性 を 示さ ず 、 グーグル の 地図 ぐらい しか 出し て こ ない 」 「 some kind of a joke （ 何 か の 冗談 ） 」 と 評し て いる と いう 。

鳩山 政権 が 誕生 し 、 移設 問題 が 紛糾 する 翌年 5 月 ごろ に 、 やはり これら 2 つ の 基地 を 含む 「 九州 ローテーション 案 」 なる もの が 鳩山 周囲 の ブレーン ら によって 提唱 さ れ て いる が ( 後述 )、 両者 の 関連 は 定か で ない 。

小川 に よれ ば 最初 に 普天間 移設 が 問題 化 し た 1996 年 頃 から 考え て い た 案 で あり 、 当時 東海大学 が 発行 し た 研究 誌 で 計画 概要 を 知る こと が 出来る 。

小川 は 県内 移設 自体 は 必要 条件 と みなし 、 日 米 安保 に 依存 し ない 場合 国防 費 が 数 倍 に 跳ね上がる 旨 を 主張 し て いる 。

日本 の 環境 アセスメント の 泰斗 として 知ら れる 島津 康男 は 、 本案 について 戦略 的 環境 アセスメント の 制度 上 から は 興味 を 示し て いる ものの 、 森林地帯 で ある キャンプ・ハンセン へ の 移設 という アイデア について は 「 著者 に は 海上 の 埋立 て を 回避 し 、 すべて を 陸上 に という 前提 が ある が 、 自然 環境 保全 ・ 地元 建設 業 の 参入 可能 性 を 想定 し て か 、 不明 の ところ あり 」 と 述べ 、 嘉手納 の 軍民 共用 化 について も 那覇空港 が 拡張 工事 を 行っ て いる こと を 挙げ て 整合 性 を 問題 視 し て いる 。

その後 も 本案 の 検討 は 無く 、 2010 年 5 月 に 鳩山 は 県 外 移設 断念 に 至っ た 。

なお 、 橋下 は 鳩山 が 辺野古 移設 の 意思 を 表明 し た 後 の 2010 年 5 月 18 日 、 「 日 米 で 合意 し て いる の だ から 、 V 字 滑走 路 案 に する べき だ 。

2009 年 12 月 4 日 、 防衛 省内 で 移設 候補 地 の 一つ として 鹿児島 県 の 種子島 の 沖 に 浮かぶ 馬毛島 が 挙がっ て いる こと が 分かっ た 。

防衛 省 は 2009 年 10 月 に 移設 先 として の 可能 性 を 検討 する ため の 現地 調査 を 伊江 ・ 下地 両島 で おこなっ て いる 。

佐賀 に 近い 大分 を 地盤 と する 社民党 幹事 長 の 重野 安正 など は 佐賀 県連 の 定期 大会 で 反対 し 、 国外 移設 を 推し て いる 。

なお 、 政府 内 で の 検討 と は 独立 に 、 鳩山 ブレーン と さ れ て い た 孫崎 享 や 田岡 俊次 が 大村 基地 へ の 移設 を 軸 に し た 案 を 鳩山 に 提案 し て いる 。

洋上 に 浮かべ た メガ フロート 上 に 滑走 路 を 建設 する 移設 案 は 現行 計画 の 策定 に当たって 一 度 は 放棄 さ れ た が 、 本案 を 推す 意見 表明 も 度々 なさ れ て いる 。

ヘリ 部隊 の 大半 を 鹿児島 県 徳之島 に 移設 する 案 。

日本 共産党 の 志位 和夫 委員 長 は 訪米 し 、 2010 年 5 月 7 日 、 ケヴィン・メア 国務省 日本 部長 、 多国 間 核 安全 部 の ジョナサン・サンボア と の 会談 で 、 「 普天間 問題 解決 の 唯一 の 道 は 、 移設 条件 なし の 撤去 しか ない 」 と 主張 し た 。

政権 として は 普天間 飛行場 の 県内 ・ 辺野古 移設 を 引き続き 進め た 。