明治４年（１８７１年）１１月１２日、岩倉、木戸、大久保、伊藤らの政府首脳に多数の随員および留学生を加えた総勢１０７名もの岩倉使節団の出発を受け、西郷、板垣、大隈の各参議、外務卿副島種臣、文部卿大木喬任、大蔵大輔井上馨、兵部大輔山県有朋、それに後日司法卿に就任する江藤新平という陣容の「留守政府」が発足した。出発を前に使節団と留守政府は職務に関する協議を行い、留守政府の主たる任務を廃藩置県の残務処理とし、重要な事件は互いに報告しあい、月２回の通信を欠かさないことを約し、その間留守政府はできるだけ新規の改正を避け、やむを得ない場合は大使に照会すること、諸官省長官の欠員の補充、官員の増加はすべきでない、とする「約定書」を交していた。だが革命直後の激動ただならぬ政治・社会情勢は、大胆かつ敏速な政策の実施を必要とし、また当初９か月とした旅程が使節団自身の失策により実に２倍以上の１年１０か月に及ぶという予想外の事態が発生する中で、即断即決、独断専行を本領とする西郷を廃藩置県の後始末のみに専念させ、それ以外は万里の彼方の使節団の承認を必須条件として彼の手足を縛ろうとしたことがそもそもの間違いであったと言わねばならない。
維新政府が直面する「近代」への移行について明確な見通しを持たない西郷が一筋縄ではいかない強者揃いの政府閣員たちをまとめるには、それぞれを信頼して仕事を任せ責任は自分が負う、ということ以外に採りうる方法はなかったであろう。それまで木戸や大久保の厳格な指導に頭を抑えられていた閣員たちは西郷の寛容な姿勢を歓迎し、彼らが念願とする政策の実現に向かって一斉に走り出す。その主なものは以下の通りである。
司法省 府県裁判所を設置（４年１２月）、
大蔵省 田畑勝手作の許可（４年１０月）、田畑永代売買の解禁（５年２月）、
地租改正の布告（５年７月）
国立銀行条例の制定と太陽暦の採用（５年１１月）、
文部省 学制の頒布（５年８月）
陸海軍省 徴兵告諭（５年１１月）、徴兵令（６年１月）
筆頭参議としてこれらの政策に承認を求められる度に西郷はその意義を熟慮したであろう。奉行所を廃止した後、政府が裁きを下すべき裁判所の設置は確かに必要である。年貢に変わる地租を貨幣で納めさせようとするなら、米より商品価値の高い作物を農民自身の選択によって栽培する自由や所有する田畑を売却する自由は当然認めるべきである。産業の発展に応じ、かつての両替商に代わる銀行を設立し、利息を払って預金を集め、より高い利息で商人たちに貸し付けて利益を得る仕組みを理解することは難しくはなかっただろう。太陽暦の採用には抵抗があったかもしれないが、世界の大勢に従うという意味では納得できただろう。教育制度や徴兵制はもちろんである。西郷はそのように理解し、大隈の鉄道建設を唯一の例外として、諸省が進める近代化政策を廃藩置県の理念を実現するために必要な措置であり、留守政府の責任において実行すべき政策とみなして次々と承認していったものと思われる。
こうして留守政府はまず順調なスタートを切ったのだが、西郷の胸中には逃れられない憂鬱が蟠（わだかま）っていた。廃藩置県に激怒し、西郷への憎しみを募らせていた旧主久光の彼に対する絶え間ない攻撃である。明治４年（１８７１年）１２月、久光は突然、鹿児島県令への就任を志願した。それは事実上久光が鹿児島県の支配者に復帰する意思を表明し、来春上京するとした約束を破棄する行為に外ならない。これを許せば他県に示しがつかないばかりか、革命の主力を担った鹿児島県において、留守政府の最高権力者と旧主の間に深刻な内紛が発生している実態を天下に知らしめることになりかねない。西郷は太政大臣三条実美の力を借りて久光の県令志願を思い止まらせたが、鹿児島に盤踞（ばんきょ）する久光を慰撫し、改めて上京に同意させるには、天皇を鹿児島に連れ出し、久光に対面させる以外に道はないと判断し、翌５年（１８７２年）５月２３日、「西国巡幸」の名目で天皇に随行して東京を出発、６月２２日鹿児島に到着する。
天皇一行を迎えた久光は衣冠束帯に威儀を正し、時局への憂慮を言上する機会を待ち望んでいたが、その機会は得られず、天皇と随行者たちの洋服姿に落胆し、玉座の周囲はあたかも異人館のようで溜息が止まらない、と子息忠義に漏らした。何よりも久光を激昂させたのは、西郷以下の薩摩藩出身の随行者たちが、滞在中誰一人としてただの一度も挨拶に来なかったことだった。巡幸の目的が久光の慰撫・説得にあったことを思えば、もっての外の冷遇と言わねばならないが、あるいは西郷は、自分たちは天皇の随行者であり、その職務中に旧主に対し臣下の礼を執るわけにはいかないと考えたのかもしれない。だがそれは封建の遺制に固執する久光の目には、忘恩の逆臣としか映りようのない不埒の所業であった。
怒り心頭に発した久光は、天皇の出発が風雨のため順延となる間に14か条の建白書を書き上げ、６月２８日、行在所（あんざいしょ。行幸中の天皇の仮宮）に参向して徳大寺宮内卿に提出した。それは、今の政体では国運は日を追って衰弱し、皇統も共和政治の悪弊に陥り、ついには洋夷の属国となる形勢、鏡に掛けて拝する如く、嘆息流涕（溜息をつき、涙を流す）の外なく御座候という激烈な政府批判に始まり、西郷、大久保の罷免を求め、これに関する天皇の質問を待つというもので、その末尾は「これも馬鹿参事どもの処置ゆえの義、悪（にく）むべきの極みに御座候」と結ばれていた。「馬鹿参事」が西郷を指すことはいうまでもない（落合弘樹著『西郷隆盛と士族』より）。天皇の政治的利用によって久光の怒りを鎮めようとした西郷の策は完全な失敗に終わり、久光の上京はさらに困難となったのである。
７月２日、天皇一行は久光の建白に応えることなく慌ただしく出発し海路神戸に向かったが、途中寄港した四国の多度津で「近衛兵沸騰」の急報に接する。それは、御親兵から改編された近衛兵たちが陸軍大輔山県有朋への不満を爆発させ、彼の罷免を求めて蹶起したという知らせであった。その前の２月、西郷は兵部省を陸軍省と海軍省に分割し、山県を陸軍大輔に任命していた（これ自体がすでに約定書に違反しているが、西郷がそれを顧慮した形跡はない）。山県は薩長土の出身藩ごとに結束を固める御親兵を廃して近衛に統一し、近衛都督、陸軍中将に任官すると、フランス式階級制度を導入して将校、下士官、兵卒の間に階級差と給与差をつけるピラミッド型の軍隊組織へと改革を進めた。近衛兵の中核を占める旧薩摩藩士族は長州人の山県が進める兵制改革への不満を高め、軍を辞して帰国する者が後を絶たない情勢となる。その数は兵員５００名、夫卒に至っては僅か４名を残すのみで１０００名が帰国する事態となっていた。そこに長州藩の奇兵隊で山県の部下だった山城屋和助という御用商人に対し、山県が巨額の陸軍資金を不正流用したという前代未聞の汚職疑惑が発覚し、薩摩藩士族を中心とする近衛兵が怒りを爆発させたという次第であった。西郷は急遽天皇一行と別れて東京に急行し、事件の解決に当たることを決断する。