開拓使は、版籍奉還(明治2年6月17日許可)を受けて7月8日に実施された官制改革「職員令」(2年7月8日)で誕生した中央政府機関であり、それまで外国官が所管していた業務中、開拓に関する部分を分離独立させたものである。
　この「職員令」体制は、形式的には「大宝令」に則る復古的色彩の強い官制改革で、「政体書」体制の8官中、神祇官が太政官とともに2官となり、大蔵省、兵部省、刑部省、外務省、民部省、宮内省の6省が太政官の下で主行政を担当する体制となっている。開拓使は太政官に直属する機関で、各省を総監する長＝卿同様に開拓使長官にも「開拓使長官　諸省卿同等タル」(「太政官日誌」『維新日誌』)との沙汰書が出て、開拓使が6省と並ぶ位置にあることが確認された。この沙汰書は、明治2(1869)年7月13日、開拓使の前身ともいうべき「蝦夷開拓督務」(6月4日任命)を命ぜられていた元佐賀藩主鍋島直正を、開拓使長官に直す沙汰書と同時に出されたものである。
　蝦夷開拓督務というのは、鍋島直正への勅書によると、直正の請願により設けられた職で、国家体制が整い国を挙げて蝦夷地開拓に着手するまで少しの間、直正に蝦夷地開拓を委ねるというものであった。直正を蝦夷開拓督務に任ずる2週間ほど前、新政府は5月21日と22日の2日にわたって、東京在留の上級官員、諸侯等を御前に集めて勅問を行った。丁度箱館では新政府軍が箱館の奪回を終えた直後であった。勅問は、皇道興隆・知藩事被任・蝦夷地開拓の3件で、蝦夷地開拓についての下問書には「(前略)箱館平定ノ上ハ、速ニ開拓教導等ノ方法ヲ施設シ、人民繁殖ノ域トナサシメラルベキ儀ニ付、利害得失、各意見無忌憚、可申出候事」(「太政官日誌」『維新日誌』)とあり、また鍋島直正への勅書でも「蝦夷開拓ハ、皇威隆替ノ関スル所、一日モ忽ニス可ラス」とあるところをみれば、鍋島はこの勅問を受けて蝦夷地開拓の任を請願したものと思われる。新政府発足以来、勅問という形をとって、政府の中枢に対してしばしば重要問題が提議されているが、蝦夷地開拓の問題は、外交問題、財政問題と並んで重要急務課題の一つであった。
　また、この蝦夷地開拓督務の任命に続いて島義勇、松浦武四郎らが蝦夷開拓御用掛に任ぜられている。この段階では地方行政機関の箱館府とは全く別の開拓専務の役所が出来るという認識が一般的であったようで、青森の廻船問屋は日記に「九月七日(略)箱館府は知府事御支配ニテ、右ニ不拘、蝦夷地開拓館箱館ヘ御造営、右総督は肥前佐賀ノ鍋島中納言様ヘ被仰付、追々御直々箱館ヘ御下りノ由」(伊東善五郎文書「五番家内通観」『青森市史』資料編1)と記している。
　しかし鍋島は、8月16日、大納言に昇任して北海道開拓から離れて行き、8月25日、公家の東久世通禧が長官に任命された。東久世は、文久3(1863)年の政変で三条実美らと共に長州落ちした(七卿落ち)尊王攘夷派公卿の1人で、王政復古で参与から議定となり、外国事務総督、外国事務局輔、横浜裁判所総督、神奈川府知事、外国官副知事など外交事務担当を歴任、開拓使長官に任命される直前には太政官事務局である弁官の長「大弁」に転じていた。「職員令」では開拓使の職務は「諸地開拓を総判」することとなっていたが、東久世長官への沙汰書(「太政官日誌」『維新日誌』)は、緊急且つ最重要課題である北海道開拓のため、現地北海道へ赴任し、開拓の指揮を取ることが前提の発令となっていた。
　またこの時期イギリス公使パークスは、箱館在留のユースデン領事から「五月に暴徒から箱館港を回復した後、同港の行政事務が混乱していること、知府事の清水谷公考が離函してしまったこと、さらに政府から派遣された担当者が権威を争い、変則な状態が続いて蝦夷地内の事件を処置しようとする様子が見えないこと、このため各国領事は誰と折衝していいのか分からなくなっている」などの報告を受け、8月22日「蝦夷地の行政組織はどのようにするのか、箱館における現在の最高責任者及び運上所業務の責任者は誰なのか」を問う書簡を外務省に寄せていた(『日本外交文書』第2巻第3冊)。政府は対外的にも箱館の処置を早急に対処しなければならなかったのである。これに対して政府は9月3日に「今般東久世通禧ヲ開拓長官ニ任ジ、其他の官員を箱館表へ被差遣、諸般の規則相立貿易上不都合無之様可取計旨、我政府より下命有之」とパークス公使へ回答し、さらに9月14日には各国公使へ蝦夷地は北海道と命名したこと、東久世開拓長官、島判官、岩村判官、得能権判官らを箱館へ派遣し、同港の貿易事務を担当させること、丸山外務大丞、岡本開拓判官、谷本外務権大丞ほかを樺太へ赴かせることを通知している(同前)。
　箱館への赴任が決定した開拓使首脳は、8月末、開拓に関する施政方針等について13項目に及ぶ伺書を太政官へ提出して指示を求めた。太政官は大蔵・刑部・外務各省の意見を徴して政府見解をまとめた(同前)。
　9月21日午前8時、政府の見解を手にした東久世長官は、チャーターしたイギリス商船テールス号(20日午後乗船)で東京品川から箱館へ向かった。
　なお、この日より10日ほど前の9月10日、箱館裁判所の時と同様に樺太の主任官に任命された岡本監輔開拓判官は、イギリス商船ヤンシー号で樺太へ向かっている。樺太の所置については、外交問題として外務省主導で対応が検討されていたため、外務省の丸山外務大丞、谷元外務権大丞らが同船していた。その後樺太開拓については、東久世長官が3年1月22日に参内して樺太開拓使分離を進言したこともあり、同年2月13日に樺太開拓使が分離された(北海道担当は北海道開拓使と呼ばれる)が、翌4年8月8日には再び合併された。この間、後に開拓長官となる黒田清隆が3年5月9日に開拓次官に就任し、樺太専務を命じられている。