박영효가 내부대신으로 재직했던 기간에 추진했던 괄목할 만한 업적 중의 하나는 지방행정제도의 개혁이었다. 8道를 기본으로 5개의 留守府, 3개의 監理署 그리고 牧·郡·縣 등으로 편제된 종래의 지방행정체제는 매우 번잡하고 비능률적이었다. 지방행정관리들은 국왕에 의해 임명되었으나 이들의 권한은 뚜렷하게 구분되어 있지 않았다. 더욱이 1894년 이전의 지방행정조직은 매관·매직 등 부패의 온상이었다. 따라서 내부대신 박영효는 지방행정의 효율성을 높임과 동시에 자신이 구상한 대개혁을 밀어줄 인물들을 지방행정기구의 요직에 부식할 것을 목적으로 기존의 행정조직을 대폭 개편하려 하였다. 앞에서 논급했던 바와 같이, 그는 1895년 1월초에 지방행정제도를 개혁하려고 시도하였다가 이노우에공사에 의해 저지당한 일이 있었다. 그러나 일본의 영향력이 쇠퇴하고 자신이 실권을 장악했던 1895년 6월에 그는 드디어 이 계획을 실천에 옮겼다.

1895년 6월 18일에 공포된 지방제도개혁에 관한 조칙 및 칙령에 의하면, 행정을 효율적으로 운영하기 어려운 大구역주의인 8도제를 폐지하고 소구역주의에 입각하여 漢城府·仁川府·忠州府 등의 23府로 편제하였으며, 종래 번잡하게 나뉘어져 있던 부·목·군·현 등을 모두 郡으로 단일화하여 총 337군을 23부 아래로 분속시켰다.⁴⁹⁰⁾≪韓末近代法令資料集≫1, 399∼402쪽. 이와 아울러 인천·부산·원산 등 3항의 감리서도 폐지하였다.

한편 종래 문란했던 지방관 인사행정의 폐해를 막고 공정한 인물을 등용하려는 취지에서 지방관리 임용제도의 개혁도 단행하였다. 그리하여 각부에 觀察使 1인, 參書官 1인, 主事 약간 명, 警務官 1인, 警務官補 1인, 巡士 2인 이상 등을 배치하였으며, 군에는 郡守 1인만을 두고 여타 직원에 관한 규정을 두지 않았다. 그리고 관찰사는 내부대신으로부터, 군수는 관찰사로부터 각각 지휘와 감독을 받도록 조치함으로써 명령계통을 분명히 했다.⁴⁹¹⁾≪韓末近代法令資料集≫1, 404∼405쪽. 아울러 근대적 중앙집권국가를 실현하고 효율적인 지방행정체제를 실시하기 위해 지방관의 권한을 축소시켰다. 각부에 경무관 등을 두어 지방경찰업무를 담당케 함으로써 종래 군사권에 포함되어 있었던 지방경찰업무를 분리시켰다. 또한＜社還條例＞를 실시하면서 지방관이 還政에 간섭하지 못하도록 명시함으로써 지방관의 수세권 행사를 제한하였으며, 지방재판소를 개설하면서 지방관의 권한에서 行刑權을 분리시켰다.⁴⁹²⁾尹貞愛,＜韓末 地方制度 改革의 硏究＞(≪歷史學報≫105, 1985), 78∼88쪽 참조.

예상대로, 박영효는 6월 26일에 23부에 관찰사를 새로 임명함으로써 지방관제를 자신의 권력기반으로 만들어 나갔다. 23명의 신임 관찰사 중 6명만이 전직 관찰사이거나 지방관이었고, 그 나머지는 박영효의 추천을 받은 인사이거나 박영효의 측근들이었다. 이러한 지방행정제도의 개혁을 통해 그는 자신의 주도하에 개혁을 전국적으로 추진할 수 있는 근거를 확보했던 셈이다.