これまでみてきたとおり、大化改新によって地方行政制度が構築されていった。国については、『日本書紀』天武十二年（六八三）十二月丙寅条に、諸国の境界を区切る作業を始めたが完了しなかったとあり、続けて同十三年十月辛巳条にも諸国の境界画定作業の記事がある。また、同天武十四年九月戊午条に、東海・東山・山陽・山陰・南海・筑紫に使者を派遣して諸国を巡察させたともあることから、この間に国境が定められ、それをベースにした畿内七道制が施行されたのであろう。
　武蔵国の史料上の確実な初見は、同天武十三年五月甲子条で、百済（くだら）から来朝した僧尼や俗人二三人を武蔵国に安置したというもので、まさに武蔵国が設置されたと推定できる時期のことである。
　この武蔵国は、現在の埼玉県・東京都と神奈川県川崎市・横浜市の大部分にわたる広大な領域を占めていた。しかしこれまでも触れてきたように、それ以前の古墳の分布をみると、武蔵野台地を巨大な空白地にして、大きく北と南に分かれている。北武蔵地域の豪族による南武蔵地域の支配を前提に、「武蔵野」を挟んだ広大な領域がヤマト王権によって統合されて武蔵国が誕生したのであろう。
　その中心となる国府は、当時の多磨（麻）郡（現在の東京都府中市）に置かれた。そこに赴任した記録上の最初の武蔵守は、引田（ひけた）朝臣祖父（おほぢ）という（『続日本紀』大宝三年〈七〇三〉七月甲午条に任命記事がある）。なぜ国内で南寄りの、つまり旧来の在地豪族の拠点である埼玉郡方面を避け、また当時の交通路（詳しくは後述）からみても不便な場所に国府が設置されたのかについては必ずしも明らかではないが、その自然地形による立地条件を考慮することも重要であろう。