光平の死後、1960年（昭和35年）に第29回衆議院議員総選挙が行われた。当時23歳で、まだ被選挙権が無かったため、地元では元参議院議員で群馬県知事、長野県知事を歴任した伊能芳雄らを立てたが落選。結果的にこの時、伊能が議席を取れなかった事が小渕の政界進出を導いた。

1962年（昭和37年）、早稲田大学を卒業、早稲田大学大学院政治学研究科に進学、在学中の1963年（昭和38年）、海外視察旅行に出かけ、当時アメリカの施政権下にあった沖縄県を皮切りに計38ヶ国を歴訪[1]。

早大大学院在学中の1963年11月、第30回衆議院議員総選挙に旧群馬3区（中選挙区制）から自民党公認で出馬し、47,350票を獲得し初当選（4議席中3位当選）。26歳という若さであった。同期には橋本龍太郎、中川一郎、大出俊、田中六助、伊東正義、渡辺美智雄などがいる。群馬3区は福田赳夫、中曽根康弘、日本社会党書記長に登りつめた山口鶴男などの大物議員が林立し「上州戦争」とも呼ばれる激戦区で、小渕は自らを「ビルの谷間のラーメン屋」[注釈 1][2]「米ソ両大国の谷間に咲くユリの花」と喩えていたが、その後も議席を維持した（連続12回当選）。

1967年（昭和42年）、現在環境保護運動家として活動する大野千鶴子と結婚した。仲人は橋本登美三郎が務めた。

自民党内では佐藤派→田中派→竹下派→小渕派と一貫して保守本流を歩き、渡部恒三、小沢一郎、橋本龍太郎らと共にいわゆる「竹下派七奉行」に列せられた。また、竹下登に一貫して師事し、竹下直系として力を握った。

1970年（昭和45年）1月20日に郵政政務次官（第3次佐藤内閣）に就任した。就任時、「郵政省で政務次官をやるからには現場の職務を深く理解したい」と考え、郵政外務職員に混じって自ら郵便配達を行い、当時の郵政省職員、郵便局局員を驚かせ、かつ支持を得ていった。こうしたパフォーマンスは、2021年現在では珍しくないが、当時としては異例で大いに話題を呼んだ[注釈 2]。

1972年（昭和47年）、自民党総裁選で田中角栄と福田赳夫が対決した『角福戦争』の際、同郷の福田ではなく、同じ派閥の田中に投票した。そのため、福田首相を熱望していた群馬県民の怒りを買い、その年の暮れに行われた、第33回衆議院議員総選挙で苦戦を強いられたが、全国最低得票で辛くも当選した。

1972年7月12日に、建設政務次官（第1次田中内閣）に就任し、1973年（昭和48年）11月25日には総理府総務副長官（第2次田中改造内閣）に就任した。このように、小渕は3回も政務次官に就任しているが、政務次官就任は当時の自民党の常識では通常2回が限度とされており、非常に異例であるといえる。

1979年（昭和54年）11月9日、総理府総務長官兼沖縄開発庁長官（第2次大平内閣）として初入閣。同期の中で国務大臣になったのは、最も遅かった。

この間、木曜クラブ常任委員会議長として、竹下登自由民主党総裁の実現に奔走。1987年（昭和62年）11月6日に発足した竹下内閣で内閣官房長官に就任し、内閣総理大臣臨時代理を務めた。官房副長官を務めた小沢一郎とのコンビは、竹下によって「小・小コンビ」（スモールコンビ）と呼ばれた。また小渕は「竹下内閣には三人の官房長官がいる。一人目は本物の私。二人目は官房長官経験がある竹下登総理、三人目は官房副長官の小沢一郎」という言葉を残している。

自由民主党群馬県支部連合会（群馬県連）では、1986年7月から会長を務めた[3]。
「平成おじさん」から首相へ1989年1月7日、総理大臣官邸にて新元号を発表

官房長官時代の1989年1月7日、昭和天皇崩御に伴い明仁親王が践祚（皇位継承）。改元にあたり、「元号法」に基づいて「元号を改める政令（昭和64年政令第1号）」が公布された後、総理大臣官邸（現：総理大臣公邸）での記者会見で「新しい元号は『平成』であります」と新元号を公表した。