同年9月自民党总裁选举中，为了赢得下次大选，各派新老议员大都支持人气颇高的桥本，河野洋平则不得不宣布退出总裁竞选。原本是桥本与河野之间的新领导竞争，最后演变为桥本与小泉纯一郎之间的“总裁竞选作秀”，桥本以304票对87票的战绩毫无悬念地击败小泉，出任自民党第17任总裁。1996年1月5日，村山首相突然提出辞职。1月11日，桥本顺利地当选为日本第82任首相，从政三十余年的桥本终于如愿以偿，登上了权力的巅峰。时隔两年半，自民党在桥本的领导下，夺回了首相宝座。
第一届桥本内阁是由自民党、社会党和先驱新党组成的三党联合政权。桥本在1月22日第136届国会施政方针演说中，高举“改革”和“创造”的旗帜，提出了重建日本经济、建设长寿社会、开展独立外交和推动行政财政改革四个最重要的课题。
然而，实际上桥本新政府首当其冲面临的一个棘手问题，就是如何处理住宅金融专门公司的坏账问题。20世纪60年代末以来，日本一些大银行组建的“住宅金融专门公司”将大量资金投向房地产，随着泡沫经济的崩溃，这些公司的坏账愈加严重，已经阻碍了日本经济的复苏。桥本准备在1996年度财政预算中追加6850亿日元，以逐步解决“住专”问题。这种做法招致国民不满和在野党反对。小泽一郎鼓动新进党国会议员轮流在国会通道上“静坐”，阻挠议员入室审议。桥本不得不做出让步，暂不讨论对“住专”的补贴问题。
1996年11月7日，第二届桥本内阁成立，时隔三年零三个月自民党又恢复了一党执政。桥本打出了六大改革的旗号，即行政改革、经济构造改革、金融体系改革、社会保障构造改革、财政构造改革和教育改革。其中成效较为显著的是以中央政府机构改革为主要内容的行政改革。桥本设立了直属首相的“行政改革会议”，排除官僚和官僚出身的人选，组成了一个包括12名财界首脑、学界泰斗的委员会，旨在“确立政治主导的行政模式”。其具体内容主要是根据1998年6月《中央省厅等改革基本法案》，改革中央行政机构，将原有的1府22省厅精简为1府12省厅；放宽限制，整顿削减特殊法人，减少政府的权限和经济职能；继续推进地方分权改革，根本改变国家与地方的存在方式，提高地方公共团体的自主性和自立性；制订《信息公开法》，提高行政机构工作的透明度等。本次行政改革作为一次“新自由主义改革”，目标是在建立“强政治弱行政、小政府大社会”的行政体制的同时，也是在冷战后的新时期，适应日本走向“政治大国”的一个重要步骤。
与日美关系相关的“冲绳问题”，是桥本从村山手中接过来的一个“烫手山芋”。本来由于苏联解体、冷战体制崩溃，日美安全合作成为一个没有对手的“拳击手”；加之日美贸易摩擦的隐患，使得日美同盟处在“风雨飘摇”之中。桥本就任首相约四个月前的1995年9月4日，爆发了驻冲绳美军强暴日本少女的恶性事件。如何处理冲绳问题，成为横亘在日美之间的一个难题。
桥本上台后，他出色地既扮演了美国最可信赖的盟友，又扮演了冲绳人最大的同情者角色。1996年1月23日，桥本将大田知事邀请到首相官邸，听取了大田提出的要求。2月23-25日，桥本闪电式地访问了美国，以求与美国总统克林顿建立亲密的“比尔”和“阿龙”的私人关系，同时他利用冲绳事件，将克林顿访日的重点从以往的经贸关系转到强化日美安全关系上。4月12日，日美双方终于达成协议，美国许诺归还冲绳普天间机场等地，而日本则同意签署《日美相互提供物资和劳务协定》，并同意修改1978年制订的《日美防卫合作指针》。
1996年4月16日，克林顿对日本进行了为期三天的正式访问。翌日，桥本与克林顿共同发表《日美安全联合宣言--面向21世纪的同盟》。该宣言的适用范围已扩大到亚太地区，适用对象也发生改变，提出了所谓亚太地区的“不稳定和不确定因素”，宣言列举了朝鲜半岛的紧张局势、核武器等军事力量的大量集中存在、悬而未决的领土问题、潜在的地区争端、大规模杀伤武器的扩散等。1997年9月23日，日美安全协商委员会发表的《日美防务合作指导方针》（即“新指针”）中又提出了“周边事态”的概念，所谓“周边事态是指对日本的和平与安全造成重大影响的事态”。其不是地理性概念，而是着眼于事态的性质“。同时，日本的军事作用显著扩大。《联合宣言》指出：日本防卫力量将在稳定亚太地区安全形势方面”发挥适当作用“。根据新《日美防卫合作指针》，日本的所谓”适当作用“是：“在日本周边地区爆发对日本和平与安全产生重要影响事态（周边事态）时”，各级政府、民间企事业团体和自卫队分别向美军提供军民用机场、港口、“后方支援”、军事情报和公海扫雷等等。并且，新指针还特意规定日本提供“后方支援”只在日本领域和“与战斗地域划清界线的日本周围海空域”进行。实际上，在现代化的远距离、快速反应作战下，前后方难以明确区分，无论提供何种形式的支援，都将被视作直接作战行为。正如日本共产党书记局长志位和夫指出：这样的话，将导致日本自动参加美军在地区内进行的任何战争行为。
桥本内阁时期的日俄关系取得了新的进展。1996年4月18日，桥本在送走克林顿后，访问了俄罗斯。这是自1985年中曾根首相出席苏共总书记契尔年科葬礼以来，日本首相时隔十一年访问莫斯科。桥本与叶利钦的会谈中，双方确认了1993年叶利钦访日时共同发表的《东京宣言》是处理双边关系的原则框架，一致同意恢复缔结和平条约的谈判。紧接着4月29日，日本防卫厅长官臼井日出男访俄，签署了日俄军事交流备忘录。防卫厅长官访俄，在双方关系历史上尚属首次。1997年1月，桥本宣布了以“多层次接触”为核心的对俄新政策。同年7月，桥本又提出了“相互信赖”、“利益互惠”、“着眼未来”的对俄政策三原则。1997年11月，桥本再次访问俄罗斯，与叶利钦举行了非正式会晤，签署了有关经济合作的“桥本-叶利钦计划”，一致同意争取在2000年前缔结和平友好条约。翌年4月，在日本川奈进行的首脑会谈中，桥本曾提出俄国确认日本对北方四岛的主权，在此基础上划定两国国境线。然而，随着叶利钦的辞职，北方四岛问题多年来没有取得多大进展。
东盟成立30周年之际，桥本首相对东盟的访问，揭开了日本与东盟关系的新篇章。1997年1月7-14日，桥本访问文莱、马来西亚、印尼、越南和新加坡等东盟五国，在新加坡发表题为《为迎接日本与东盟的新时代而改革--建立更深更广的伙伴关系》的演说。香港《亚洲新闻》的评论认为，日本此次对东盟政策的调整“是日本在外交上的又一个里程碑”。日本外务省的目的，就是要在这次访问中发表与“福田主义”同等重要的“桥本主义”。同年12月，时隔10年，第三届日本-东盟首脑会议在马来西亚首都吉隆坡举行，原本双方不定期的首脑会议，从此作为惯例每年召开。日本成为第一个定期参加东盟首脑会议的大国。会后双方发表联合声明，重申面向21世纪，加强首脑对话，尤其是在政治安全领域的对话与交流，以及人员、文化、经济方面的合作。这是自福田1977年访问东盟以来双方发表的第一个联合声明。
对华关系中的桥本，同样体现了日本政治家复杂的多面性。一方面是在出任首相前曾否定日本侵略，坚持参拜靖国神社，给人以一副鹰派的强硬色彩；另一方面又是重视对华关系，当政时以及引退之后，多次率团访华，致力于推进中日关系，被日本右翼指责为“亲中”、“媚华”的“卖国贼”。