新政府は未だ財政的・軍事的・制度的基礎が固まっておらず、大久保・木戸らの策謀に強い憤りを抱いていた土佐藩主山内容堂や自らを出し抜いた家臣に反感を抱いていた薩摩藩主島津久光、長州藩主毛利敬親らは早々に所領に引き篭もった。特に、朱子学の教養と水戸学の歴史観を持つ保守思想家の島津久光の下には、武士階級の復活を願う全国の士族が集まり封建党など様々な士族結社が結成されていた[14]。この状況から新政府は大久保利通らを薩摩藩に派遣して説得に当たらせたが、明治3年（1870年）2月24日に久光は明治政府を「洋夷の属国」として罵倒し、内閣顧問に任命される明治6年（1873年）まで上京に応じなかった[15]。

かくして、新政府は諸大名の反発を買わぬために、版籍奉還、廃藩置県と段階的な郡県制への移行を進めた。1869年（明治2年）1月14日、京都で薩摩・長州・土佐三藩の会合が京都円山で持たれ、薩摩から大久保、長州から広沢真臣、土佐から板垣退助が出席した。そして三藩主連名で土地・人民を朝廷に返上する旨の建白書を提出することで合意した[16]。また薩長土の三藩は副島種臣に働きかけて、肥前佐賀藩主・鍋島直正を動かした[17] 結果、同20日に薩摩・長州・土佐・肥前の四藩の藩主から版籍奉還の上表が朝廷に提出され[18]、他の諸藩も領地と領民を天皇に返上する上表を次々と提出した（版籍奉還）。

これに伴い、各藩主の処遇が新政府内で話し合われ、大久保ら薩摩の官吏は藩主を藩知事とし、世襲制にすべきと主張したのに対し、木戸ら長州の官吏は反対した。最終的に両者の主張を折衷する形で、藩主はそのまま藩知事に任命されたが、世襲制は否定された。また、これを機に公卿・諸侯の呼称を廃して華族と改称し、上・中・下士の区別をやめ全て士族としたほか、知事の家禄を石高の十分の一に限定し、藩政と知事家政を分離した。これにより、建前として知事と士族の間の君臣関係が消滅し、各藩は済し崩し的に自立性を奪われて明治政府の地方行政単位に転化した[19]。また、新政府内においても、王政復古時の五藩から、版籍奉還を真っ先に上表した薩長土肥の四藩が主導権を握るようになり[注釈 10]、越前・尾張・芸州の影響力は低下した[18]。

版籍奉還直後の7月8日に、職員令により官制を改革し、祭政一致を建前に神祇官、太政官を置いて前者を上位とし、太政官に左大臣と右大臣、大納言、参議、顧問として待詔院を置いた。人選は大久保の発案で、三条実美（右大臣）、岩倉具視（大納言）、副島種臣（参議）、前原一誠（参議）、待詔院学士は大久保利通、木戸孝允、板垣退助の3名を選出し、薩長土三藩の維新の功臣を激務から外して木戸派官吏の追い出しを図った[20] が、その後長州派官吏も廣澤真臣を参議に推して対抗し内政の主導権争いが続いた。その後、政体書の規定を以て高官公選の互選も行われ、輔相には三条実美（公家）、議定には岩倉具視（公家）、鍋島直正（佐賀藩主）、徳大寺実則（公卿）、参与には大久保利通（薩摩藩士）、木戸孝允（長州藩士）、副島種臣（佐賀藩士）、東久世通禧（公家）、後藤象二郎（土佐藩士）、板垣退助（土佐藩士）の10名を選出した。これにより、議定だった諸大名や公卿の多くは免職となり、麝香間祗候か他職に追いやられ、薩長土肥以外の参与も、越前の由利以外は免職となった[21]。9月に入ると王政復古の論功行賞として「賞典禄」を与えた。

新政府が外交方針として開国を決めたことは尊王攘夷派の怒りを買った。明治2年のうちに横井小楠・大村益次郎が早々に暗殺され、長州藩においては同年12月1日に大楽源太郎率いる奇兵隊や遊撃隊等の諸隊が乱を起こし、木戸が鎮圧に当たる始末となり、1870年（明治3年）5月には米沢藩士雲井龍雄の反政府陰謀事件が発覚した。1871年（明治4年）には二卿事件や久留米藩難事件、征韓を企画した外務権大丞丸山作楽の逮捕事件が勃発した[22]。このように新政府がその基盤を置いた薩長でさえも、洋式装備に統一され実戦的訓練を受けた軍隊を擁しており、成立間もない新政府にとって不気味な存在であった。ましてや静岡藩をはじめとする親藩・譜代の諸藩の動静には過敏になっていた。その結果、雲井龍雄処刑の責任者であった広沢が1871年（明治4年）1月9日に暗殺されるなど片翼飛行を始めた。また、国政を薩長土肥が独占していたことも批判を浴び、明治3年7月26日には薩摩藩士横山正太郎が集議院門前で抗議の切腹を行った。政府内では薩長土肥の対立に加え、太政官と民部省、大蔵省をめぐって大久保と木戸が対立し、薩長間で抗争が繰り広げられており、世情は不安定だった[23]。

こうした中で、政府は9月に「藩制」を公布し、藩への統制をさらに強めた[24]。藩に共通する職制、財政の規定を示し、重要な賞罰は政府の許可を得ることや、藩士身分の単純化、藩債、藩札の整理を命じた。他方、政府への不満を抑えるため、11月29日、藩地に帰郷した島津久光と、藩政改革を通して薩摩藩の軍備強化に努め、全国から集結した士族約1万2千人の兵士軍団を束ねて政府を無言で威圧していた西郷隆盛に上京するよう説得するため、岩倉具視が勅使として、大久保利通・木戸孝允が随員として鹿児島に向かい、西郷の受諾を得てようやく政権を安定させた[25]。

こうして世情が安定すると、政府は1871年（明治4年）7月にまず薩長土の3藩から御親兵を募って中央の軍事力を固め、次いで一挙に廃藩置県を断行した。全国の261藩は廃止され、3府302県に変わり、日本は中央集権的統一国家となった。藩知事と士族の禄は保障され、藩債を肩代わりした。身分制度の改革を行い、大名・公家を華族とする華族制度（日本国憲法が施行されるまで存在した、西洋式に倣った日本の貴族制度）の創設と、武士身分を士族として、農工商民（百姓・町人）などを平民とし、日本人（大和民族）は皆「国民」（明治憲法下では「臣民」とも呼ばれた）とされ、日本国民全員に苗字の公称を認めた四民（士農工商）平等政策を取った。