東横線では、渋谷側と横浜側の両端部で新たなネットワーク形成のための工事が進んだ。

横浜側は、「みなとみらい21線」との相互直通運転に向けた工事である。同線は、みなとみらい21地区を縦断する4.1kmの路線で、第三セクターの横浜高速鉄道（第6章参照）が1992（平成4）年11月に「みなとみらい中央〜元町」間（駅名はいずれも当時の仮称）の工事に着手した。1995年2月に「横浜〜みなとみらい中央」間（同）が着工すると共に、当社は横浜駅の地下化工事に着手した。これと併せて、横浜市の事業として、横浜駅を東西に結ぶ自由通路を新たに2本設けて、合計3本の自由通路が確保されることとなった。

当社の工事概要は、新しい横浜駅は、深さ22mの地下四層構造とし、東横線は東白楽駅を過ぎたところから横浜駅に至る約2.1kmを地下化し、途中の反町駅は深さ25mの四層からなる地下構造の駅にする、というもの。1996年には、東白楽〜横浜間の地下化工事に順次着手。東白楽近くの比較的浅い区間と駅部は開削工法で、そのほかはシールド工法のほか、一般的には山岳トンネルの掘削で用いられるNATM（New Austrian Tunneling Method）工法を用い、営業線の直下に地下構造物を構築するという難工事に挑んだ。

「みなとみらい21線」との相互直通運転に伴って、当社は東横線の横浜〜桜木町間を廃止にすることとし､1987（昭和62）年6月には横浜市と共に廃止区間にあたる地元との協議に入っていた。桜木町にはJR根岸線と横浜市営地下鉄（ブルーライン）の駅があり、西南方面には京浜急行日ノ出町駅もあって、交通の便は必要十分と考えられ、また東横線では横浜〜桜木町間の利用者が比較的少なかったため、廃線に支障はないものと、横浜市と当社は受け止めていた。しかし、地元説明会では、桜木町駅近くの野毛地区の住民から廃線反対の声が上がり、廃線に伴う地元振興策のあり方も含めて、協議することとなった。地元振興の方策について意見交換を行い、廃線跡地の有効利用や、横浜市営地下鉄桜木町駅と野毛地区のアクセス向上策、新たな街づくりのための支援策を提案し、先行的に施策を講じて効果確認をするなどして、地元と折衝を重ねた。時間を要したが、廃線後の野毛地区振興策についての地元の了解を経て、廃線の1年前となる2003年1月30日に、2004年1月31日を廃止日とする、東横線横浜〜桜木町間の鉄道事業廃止届出書を国土交通大臣に提出した。

東横線と「みなとみらい線（2003年7月に、路線名を略称で表示することを決定）」の相互直通運転開始は2004年2月1日に決定。

当社は横浜高速鉄道から「みなとみらい線」内の運転業務を委託され、渋谷駅から元町・中華街駅まで、当社の乗務員が運行することとなった。また、みなとみらい線の駅数は、計画段階から1駅を増やして全6駅となった。

当社は、開業前の2003年11月に東白楽駅付近の工事ヤードから車両（当社9000系と当社5000系に準じた横浜高速鉄道Y500系各1編成）を地下に搬入し、試運転と習熟運転を重ねた。そして、2004年1月30日の終電後に、これまでも実績を重ねたSTRUM工法（直上直下切替工法）で、一晩で東白楽～横浜間を地下化し、翌1月31日は渋谷～横浜間のみで営業運転をした。

また、同年1月30日の終電をもって営業終了した地上の横浜駅と高島町・桜木町の両駅には、営業終了が近づくにつれ多くの利用客が訪れ、廃線を惜しむと共に、最終列車の出発時には「野毛地区街づくり会」から会長のあいさつと駅長、乗務員への花束贈呈が行われた。

こうして、東横線とみなとみらい線の相互直通運転がスタートし、横浜の人気エリアとのネットワークがつながった。

副都心線は、1972（昭和47）年の都市交通審議会答申第15号において都市高速鉄道13号線として計画された。当初は、埼玉県志木から和光市、成増、池袋を経て新宿に至る路線とされ、1983年には営団有楽町線との共用区間として成増〜池袋間が開業した。1985年の運輸政策審議会答申第7号では、改めて志木からの路線として設定されると共に、終点は新宿から渋谷まで延伸することが示された。営団地下鉄（以下、営団）は、池袋〜渋谷間の鉄道事業免許を1999（平成11）年に取得し、2001年6月に建設工事に着手した。とくに池袋〜渋谷間は山手線の代替機能を担うことが期待され、三大副都心である池袋、新宿、渋谷を高速で結ぶ急行列車の運行も計画された。

さらに、2000年1月の運輸政策審議会答申第18号には、「既設路線の改良等」の一つとして「東横線渋谷と代官山間を地下化し、渋谷駅で営団13号線との相互直通運転化を行うことにより、東武鉄道東上線・西武鉄道池袋線、営団13号線、当社東横線・横浜高速鉄道みなとみらい21線の各線のネットワーク化を図る」という構想が盛り込まれた。

営団13号線との相互直通運転（以下、相直）については、かねてから当社内でも将来構想の一つとして議論を重ねていた計画であった。渋谷駅のターミナル機能がそこなわれて単なる通過駅になってしまうのではないか、ターミナル百貨店として長年親しまれてきた東急百貨店東横店が、伊勢丹新宿店や1996年に開業したばかりの髙島屋新宿店に客足を奪われるのではないか、などの慎重な意見もあった。

最終的には、沿線住民の利便性を第一に考えて、広域の鉄道ネットワーク構築を優先することとし、その一方で、相直開始という一大転機を、渋谷の魅力をこれまで以上に向上させる契機とすることが、将来にわたって企業価値の向上につながると判断。2002年1月に、東横線と営団13号線の相直実施を決定した。

さらに同年5月には、開業から45年以上を経て、老朽化も指摘されていた東急文化会館を閉鎖・解体し、渋谷〜代官山間地下化工事の工事ヤードとして暫定利用することを発表し、明治通りの直下に地下構造の新しい渋谷駅を建設する工事に着手した。

従来の東横線渋谷駅は8両編成に対応したホームであったが、営団13号線に合わせて10両編成に対応した長さで、2面4線のホームを整備することとした。代官山までの地下化工事については、既存高架橋やJR線をはじめとした地上構造物が与える影響や、同線との交差部東側に存在し速度を落とさざるを得なかった急曲線などの線形、工事方法などについて関係者と協議を進めた。

副都心線（営団13号線の路線名称）との相直開始は、2013年3月になる。

東横線は、これまで沿線人口の増加に対応して輸送力を確保することを重視するため、速達性はある程度犠牲にせざるを得ない状況であった。速達列車として「急行」を運行していたが、停車駅が多く、とくに朝間は運行本数が多いため、列車間隔が短くなることに伴う低速運転が常態化しており、これに複々線化工事による工事区間の徐行運転も重なっていた。そのため、利用客からは、渋谷〜横浜間の所要時間は各駅停車と急行で大きく変わらない、と受け止められ、「スピードが遅い路線」というイメージになっていた。

前述のように目黒線と営団南北線・都営三田線の相直を2000（平成12）年9月に開始したことで、東横線利用客の目黒線への転化が進み、運転間隔を広げる余裕が出てきた。また一方、JR東日本が新しい運行系統の一つとして、「湘南新宿ライン」を計画していた。横浜～新宿間が直通となり、速達性の高い列車の運行となるため、東横線の競合路線になることが見込まれた。

こうした背景から、2001年3月にダイヤ改正を実施した。新ダイヤのポイントは、当社で初めての「特急」（東横特急）を設けたこと。昼間と夕間に運行し、停車駅は自由が丘、武蔵小杉、菊名、横浜のみ（のちに中目黒を追加）で、渋谷〜横浜間の最短所要時間が4分以上短縮されることとなった。また、平日朝間の上り方向の運転間隔を2分15秒（1時間に27本）から2分25秒（1時間に25本）に変更してスピードアップを図り、急行については渋谷〜横浜間の所要時間が3分30秒短縮された。

このダイヤ改正においては、渋谷・横浜の都市間利用者と、沿線住民の利便性を両立させることを目標とし、需要予測をもとに、停車駅と運転本数を変えた10パターンのダイヤ案を作成。速達性や他社線との接続性はもちろん、優等列車（特急・急行）と各駅停車の乗換にも便利なダイヤ編成とした。

さらに2003年3月のダイヤ改正では､当社線各線との接続を考慮したうえで、停車駅に日吉駅を加えた「通勤特急」（主に朝夕のラッシュ時に運行）を新設。これにより広域のネットワーク形成が緻密となって、利便性と速達性がいちだんと高まった。

新設にあたって全社で大きくPRを展開した「特急」は、利用客にもおおむね好意的に迎え入れられ、渋谷〜横浜間の直通旅客が増加。沿線内の輸送需要のみならず、都市間輸送の需要にも応えられる路線に生まれ変わった。

なお、JR湘南新宿ラインは、この二つのダイヤ改正の間、2001年12月に運行を開始している。