1957年11月17日、旧岐阜1区の柳原三郎衆議院議員の手伝いをしていた岐阜県美濃市出身の女性と結婚[8][9]。

1958年3月29日、河野が急死。後継候補の一人に押し上げられるが、三木武夫の判断で妻の河野孝子が地盤を引き継ぐこととなった[10]。同年4月20日、孝子の秘書となり[9]、5月22日に行われた第28回衆議院議員総選挙で孝子は初当選した。
衆議院議員初当選当時の海部（『週刊サンケイ』1960年12月26日号より）1度目の文部大臣時代の海部（1976年ごろ）

1960年9月16日、河野孝子の代わりに、秘書の海部が次期衆院選・旧愛知県第3区に立候補することが決定[11]。同年11月20日に行われた第29回衆議院議員総選挙で全国最年少で初当選した[12]。

1960年12月、自民党青年局学生部長に就任。1964年、青年海外協力隊の構想をまとめ、アフリカを横断調査。同団体の創設に力を注いだ[13]。1965年には自民党青年局長となった。

1971年ごろまで一宮市新生で借家住まいをし、その後、同市平和一丁目に自宅兼事務所を構えた[14]。

三木派が河本派に移行してからは、1994年に離党するまでの間、名実共にナンバー2として河本敏夫を支えたが、河本とは対照的に資金的な貢献が少なかったため、「財布閉じ器」と渾名された。ニューリーダーの次を狙う政治家として橋本龍太郎、藤波孝生らと共に「ネオ・ニューリーダー」と呼ばれた。早稲田大学雄弁会の先輩である竹下登ら早大出身者との親交が深かったため、「現住所河本派・本籍竹下派」ともいわれた。「竹下が総理になった暁には、河本派を離脱して竹下のもとに馳せ参じるのでは」と囁かれたこともある。

1966年に労働政務次官、1972年に衆議院議院運営委員長[9]、1973年に自民党人事局長、1974年に自民党副幹事長などの要職を歴任する。

1974年には、三木内閣の内閣官房副長官に就任する。内閣官房長官の井出一太郎の代わりにランブイエ・サミットの調整を行い、1975年スト権スト問題の時には、政府の窓口として労政交渉や野党対応、マスコミ討論を担当する[15]。

1976年9月、自民党国会対策委員長に就任[9]。同年12月、福田赳夫内閣で文部大臣として初入閣を果たした。石原慎太郎とともに昭和生まれ初の大臣であった。1985年、第2次中曽根内閣で再び文部大臣を務めた。文部大臣時代の業績として、「共通一次試験」の導入が挙げられる。
自由民主党総裁

1989年7月24日、宇野宗佑首相が第15回参議院議員通常選挙敗北の責任をとり辞意を表明。「1989年8月自由民主党総裁選挙」も参照

当時、主な有力議員は軒並みリクルート事件に関与していた。中曽根康弘は責任をとって離党。安倍晋太郎、宮澤喜一、渡辺美智雄らニューリーダーは自民党が定めた「1年間、もしくは次の総選挙まで党の役職を辞退する」という内規の対象となり謹慎中の身であり[16]、四大派閥（竹下派・安倍派・宮澤派・旧中曽根派）はいずれも後釜の総裁候補を出せる状態になかった。

宇野が辞意を表明した7月24日、安倍が退院した[17]。同日、小沢一郎、梶山静六、奥田敬和ら竹下派幹部は意見交換した。どの派もリーダーが総理になる前にナンバー2が手を挙げるわけにはいかない事情があったが[18]、梶山はこの席で「橋本総裁でもいい」と発言。特に異論は起こらなかったため、一部に「橋本氏擁立」との情報が伝わった[19]。

竹下の意中の候補は早稲田大学雄弁会の後輩で親しい関係にある海部であった。クリーンなイメージはリクルート後には相応しかったし、再登板も視野に影響力を維持したい竹下にとっては、若くはあるが決定的な世代交代に至らないという点でも好ましかった。何より、中小派閥の出身で独自に強い政治基盤を持たない海部は、竹下にとって統制しやすい存在でもあった。当時、竹下と海部はTBRビルに事務所を構えていた。竹下は4階、海部は10階。竹下に呼ばれた海部は7月26日、人目を忍ぶように竹下事務所に足を運んだ。竹下は、自派からの橋本龍太郎擁立は難しいことを海部に伝えた。ここから「海部俊樹首相」への道が始まった[20]。7月27日、安倍は竹下を私邸に訪ね、ポスト宇野の選出方法について意見交換した[17]。

三番町の自宅マンションの電話は朝から深夜まで鳴りっぱなしであった。議員や記者が連日押しかけてきた。7月29日、海部は妻と長男と長女を車に乗せ、逃れるように八ヶ岳のふもとのホテルに向かった。このころには海部も覚悟を決めていた。「俺も政治家として死ななきゃならんのだから、その前に精一杯のことをしたい」と家族に伝えるが、全員から反対される。二泊し、東京へ帰る車中でようやく妻が折れた[21]。

7月30日、元麻布の金丸邸に小渕恵三、小沢一郎、奥田敬和、梶山静六、羽田孜、渡部恒三ら竹下派幹部が顔を揃えた。ただしそこに橋本の姿だけがなかった。橋本への一本化は100人を超える派閥の分裂につながりかねなかったため、金丸は「橋本君にはもう少し人間修業をしてもらう」と述べた[22]。7月31日、竹下派は常任幹事会を開き、自派の候補者擁立を見送る方針を正式に確認した。同日、橋本は不出馬を表明[23]。

竹下派の派内調整が進行する中で、河本派内では領袖の河本敏夫の擁立の動きが続いていた。すでに78歳であったが、最後のチャンスと総裁選出馬への意欲を見せた。8月2日、河本は自派議員から個別に意見を聞く一方、安倍、金丸らと意見調整するが、説得された結果、出馬を断念した[24]。同日、海部は記者会見し、出馬表明した[25]。

同年8月8日に行われた自由民主党総裁選挙には、海部のほか、宮澤派の支援を受けた二階堂派の林義郎、安倍派の石原慎太郎が立候補。いずれも派閥の長ではないという点で当時としては異例な総裁選となったが、最大派閥の竹下派の支持を得た海部が両者をおさえて自由民主党総裁に選ばれた。
内閣総理大臣1990年7月7日、ヒューストンにてアメリカ合衆国大統領ジョージ・H・W・ブッシュ（左）と1991年4月18日、赤坂迎賓館にてソ連大統領ミハイル・ゴルバチョフ（左）と1991年7月15日、ロンドンで開催された第17回先進7か国首脳会議にて