明治3年（1870年）2月13日、西郷は村田新八・大山巌・池上四郎らを伴って長州藩に赴き、奇兵隊脱隊騒擾の状を視察し、奇兵隊からの助援の請を断わり、藩知事毛利広封に謁見したのちに鹿児島へ帰った。同年7月27日、鹿児島藩士・集議院徴士横山安武（森有礼の実兄）が時勢を非難する諫言書を太政官正院の門に投じて自刃した。これに衝撃を受けた西郷は、役人の驕奢により新政府から人心が離れつつあり、薩摩人がその悪弊に染まることを憂慮して[5]、薩摩出身の心ある軍人・役人だけでも鹿児島に帰らせるために、9月、池上を東京へ派遣した[6]。 12月、危機感を抱いた政府から勅使岩倉具視・副使大久保利通が西郷の出仕を促すために鹿児島へ派遣され、西郷と交渉したが難航し、欧州視察から帰国した西郷従道の説得でようやく政治改革のために上京することを承諾した。
明治4年（1871年）1月3日、西郷と大久保は池上を伴い「政府改革案」を以て上京するため鹿児島を出帆した。8日、西郷・大久保らは木戸を訪問して会談した。16日、西郷・大久保・木戸・池上らは三田尻を出航して土佐に向かった。17日、西郷一行は土佐に到着し、藩知事山内豊範・板垣退助と会談した。22日、西郷・大久保・木戸・板垣・池上らは神戸に着き、大坂で山縣有朋と会談し、一同そろって大坂を出航し東京へ向かった。東京に着いた一行は2月8日に会談し、御親兵の創設を決めた。この後、池上を伴って鹿児島へ帰る途中、横浜で青年東郷平八郎に会い、勉強するように励ました[7]。
2月13日に鹿児島藩・山口藩・高知藩の兵を徴し、御親兵に編成する旨の命令が出されたので、西郷は忠義を奉じ、常備隊4大隊約5000名を率いて上京し、4月21日に東京市ヶ谷旧尾張藩邸に駐屯した。この御親兵以外にも東山道鎮台（石巻）と西海道鎮台（小倉）を設置し、これらの武力を背景に、6月25日から内閣人員の入れ替えを始めた。このときに西郷は再び正三位に叙せられた。7月5日、制度取調会の議長となり、6日に委員の決定権委任の勅許を得た。これより新官制・内閣人事・廃藩置県等を審議し、大久保・木戸らと公私にわたって議論し、朝議を経て、14日、天皇が在京の藩知事（旧藩主）を集め、廃藩置県の詔書を出した。また、この間に新官制の決定や内閣人事も順次行い、7月29日頃には以下のような顔ぶれになった[8]（ただし、外務卿岩倉の右大臣兼任だけは10月中旬にずれ込んだ）。
太政大臣（三条実美）
右大臣兼外務卿（岩倉具視）
参議（西郷隆盛、木戸孝允、板垣退助、大隈重信）
大蔵卿（大久保利通）
文部卿（大木喬任）
兵部大輔（山縣有朋）
大蔵大輔（井上馨）
文部大輔（江藤新平）
工部大輔（後藤象二郎）
司法大輔（佐々木高行）
宮内大輔（万里小路博房）
外務大輔（寺島宗則）
この経緯については、各藩主に御親兵として兵力を供出させ、手足をもいだ状態で、廃藩置県をいきなり断行するなど言わば騙し討ちに近い形であった。
明治4年（1871年）11月12日、三条・西郷らに留守内閣（留守政府）をまかせ、特命全権大使岩倉具視、副使木戸孝允・大久保利通・伊藤博文・山口尚芳ら外交使節団が条約改正のために横浜から欧米各国へ出発した（随員中に宮内大丞村田新八もいた）。西郷らは明治4年（1871年）からの官制・軍制の改革および警察制度の整備を続け、5年（1872年）2月には兵部省を廃止して陸軍省・海軍省を置き、3月には御親兵を廃止して近衛兵を置いた。5月から7月にかけては天皇の関西・中国・西国巡幸に随行した。鹿児島行幸から帰る途中、近衛兵の紛議を知り、急ぎ帰京して解決をはかり、7月29日、陸軍元帥兼参議に任命された。このときに山城屋事件で多額の軍事費を使い込んだ近衛都督山縣有朋が辞任したため、薩長の均衡をとるために三弟西郷従道を近衛副都督から解任した。明治6年5月に徴兵令が実施されたのに伴い、元帥が廃止されたので、西郷は陸軍大将兼参議となった。
なお、明治4年（1871年）11月の岩倉使節出発から明治6年（1873年）9月の岩倉帰国までの間に西郷主導留守内閣が施行した主な政策は以下の通りである。
府県の統廃合（3府72県）
陸軍省・海軍省の設置
学制の制定
国立銀行条例公布
太陽暦の採用
徴兵令の布告
キリスト教禁制の高札の撤廃
地租改正条例の布告
対朝鮮（当時は李氏朝鮮）問題は、明治元年（1868年）に李朝が維新政府の国書の受け取りを拒絶したことに端を発しているが、この国書受け取りと朝鮮との修好条約締結問題は留守内閣時にも一向に進展していなかった。そこで、進展しない原因とその対策を知る必要があって、西郷・板垣退助・副島種臣らは、調査のために、明治5年（1872年）8月15日に池上四郎・武市正幹・彭城中平を清国・ロシア・朝鮮探偵として満洲に派遣し（鹿児島県史料・忠義公史料』第7巻）、27日に北村重頼・河村洋与・別府晋介（景長）を花房外務大丞随員（実際は変装しての探偵）として釜山に派遣した[9]。
明治6年（1873年）の対朝鮮問題をめぐる政府首脳の軋轢は、6月に外務少記森山茂が釜山から帰って、李朝政府が日本の国書を拒絶したうえ、使節を侮辱し、居留民の安全が脅かされているので、朝鮮から撤退するか、武力で修好条約を締結させるかの裁決が必要であると報告し、それを外務少輔上野景範が内閣に議案として提出したことに始まる。この議案は6月12日から7参議により審議された。
議案は当初、板垣が武力による修好条約締結（征韓論）を主張したのに対し、西郷は武力を不可として、自分が旧例の服装で全権大使になる（遣韓大使論）と主張して対立した。しかし、数度に及ぶ説得で、方法・人選で反対していた板垣と外務卿の副島が8月初めに西郷案に同意した。西郷派遣については、16日に三条実美の同意を得て、17日の閣議で決定された。しかし、三条が天皇に報告したとき、「岩倉具視の帰朝を待って、岩倉と熟議して奏上せよ」との勅旨があったので、発表は岩倉帰国まで待つことになった。
以上の時点までは、西郷・板垣・副島らは大使派遣の方向で事態は進行するものと考えていた。ところが、9月、岩倉が帰国すると、先に外遊から帰国していた木戸孝允・大久保利通らの内治優先論が表面化してきた。大久保らが参議に加わった9月14日の閣議では大使派遣問題は議決できず、15日の再議で西郷派遣に決定した。