「電子政府」の言葉が、はじめて使われたのは、1997年12月20日に改定された「行政情報化推進基本計画」であろう。当初の行政情報化推進基本計画は、1994年12月25日閣議決定されたもので、計画期間は1995年度を初年度とする５か年となっていた。しかし、社会的な状況の変化に対応することが必要として、計画期間中にもかかわらず改定が行なわれた。新しい計画は、1998年度から2002年度までを計画期間とし、「21世紀初頭に高度に情報化された行政、すなわち『電子政府』の実現を目指す」ことが目標となっている。
本来、行政情報化推進基本計画は、国の行政機関を対象としたものであり、改定前には「国・地方公共団体を通じた連携・協力の在り方を検討する」となっていた。しかし、改定後は、「地方公共団体との連携」の項が新たに設けられ、住民基本台帳ネットワークシステムの利用方策や霞が関WANの活用等による国・地方間の情報の相互利用方策を検討することが、「国・地方を通ずる総合的な行政情報化を積極的に推進するため」として盛り込まれた。
翌1998年11月9日、「高度情報通信社会推進に向けた基本方針」が、1994年8月内閣に設置された高度情報通信社会推進本部によって改定（当初方針は1995年2月に決定）された。新しい基本方針には、改定された「行政情報化推進基本計画」を受ける形で、「21世紀初頭に高度に情報化された行政、すなわち『電子政府』の実現を目指す」と明記されている。
「21世紀初頭」を目標とすることは、経済競争力会議（1999年3月19日設置）での議論をもとに、小渕政権が1999年12月19日に決定した「ミレニアム・プロジェクト」にも、「21世紀初頭にも世界でも最高水準の電子政府（ Electronic Government ）の実現を図る」と引き継がれた。この文書で初めて「2003年度までに、民間から政府、政府から民間への行政手続をインターネットを利用しペーパーレスで行なえる電子政府の基盤を構築する」と、2003年度が目標年次として登場した。ただし、2003年度までに構築されるのは、あくまでも「基盤」である。
なお、自治体との関係では、「総合行政ネットワーク」の実証実験と、「2003年度までに、各地方公共団体の自主的な取り組みにより、総合行政ネットワークの整備と国の霞ヶ関WANとの接続が図られることを期待する」と、「行政情報化推進基本計画」の枠内での、極めて弱い表現になっており、この後の「e-Japan戦略」における押しつけがましさとは、大きく異なっている。
自治省・地域IT推進本部が、翌2000年8月28日に策定した「IT革命に対応した地方公共団体における情報化施策等の推進に関する指針」も、「2003年度までに電子政府の基盤を構築するという国の方針を踏まえ」としているだけで、それ以上の具体的な目標年度は明示していない。