Der Vorgänger von FC Tokyo, der Tokyo Gas Football Club, wurde 1935 gegründet. Das Team, das in der Tokyo-Liga spielte, stieg 1986 in die Kanto-Liga auf und erreichte im ersten Jahr einen hervorragenden 4. Platz. 1991 gewann es das landesweite Regional-Liga-Finale und stieg in die JSL 2. Division auf. Ab 1992 nahm das Team an der JFL teil und hielt sich ab 1995 stets in den oberen Rängen der JFL, während es die Gründung der J-League 1993 beobachtete. Im Emperor's Cup 1997 erzielte das Team einen Durchbruch, indem es drei J-League-Teams in Folge besiegte und ins Halbfinale einzog. In der letzten Saison der JFL 1998 errang es schließlich den lang ersehnten ersten Meistertitel.

Im Jahr 1999, als der Teamname in „FC Tokyo“ geändert wurde und der Verein in die zweite Liga der J-League (J2) eintrat, erreichte man im erstmals teilgenommenen Yamazaki Nabisco Cup das Halbfinale, indem man drei J1-Teams in Folge besiegte, und Yukihiko SATO erhielt den New Hero Award. In der Liga kämpfte das Team zwar gegen Ende, erreichte aber dennoch den zweiten Platz und sicherte sich den Aufstieg in die erste Liga der J-League (J1).

Im Jahr 2000, als der Aufstieg in die J1 gelang, startete das Team in der 1. Phase mit drei Siegen in Folge und erreichte den 6. Platz, in der 2. Phase gelang ein Start mit fünf Siegen in Folge, was zu einem 8. Platz (7. Platz insgesamt) führte und einen "Tokio-Sturm" auslöste. Im darauffolgenden Jahr 2001 wurde das Heimstadion, das Tokyo Stadium (heute Ajinomoto Stadium), eröffnet, und beim Eröffnungsspiel am 10. März wurde Verdy besiegt. Danach hielt das Team mit einem 9. Platz in der 1. Phase und einem 8. Platz in der 2. Phase (8. Platz insgesamt) eine mittlere Position und etablierte sich im zweiten Jahr fest in der J1. Nach Saisonende trat Trainer Kiyoshi OKUMA, der das Team sieben Jahre lang geführt hatte, zurück, und ab der Saison 2002 übernahm Hiromi HARA das Traineramt. Das Team betrat eine neue Phase, basierend auf der von OKUMA aufgebauten "Hartnäckigkeit, niemals aufzugeben" und dem "Geist, stets sein Bestes zu geben", und verfolgte unter dem neuen Trainer HARA die Philosophie des "angriffslustigen Fußballs".

Im Jahr 2002 kam es zu zahlreichen Verletzungen bei den Stammspielern, sodass das Team in der 1. Phase auf dem 10. Platz stagnierte. In der 2. Phase hingegen trugen das Wachstum und die Leistungen der jungen Spieler dazu bei, den 5. Platz (Gesamtjahresrang 9) zu erreichen, wodurch sich der von Trainer Hara angestrebte offensive Fußball allmählich durchsetzte. 2003, mit der Abschaffung der Verlängerung, wurde das Motto „90 Minuten offensiver Fußball“ ausgegeben. In der 1. Phase erreichte das Team mit den wenigsten Gegentoren den besten 4. Platz der Vereinsgeschichte, und in der folgenden 2. Phase kämpfte es bis zum Schluss um die Meisterschaft mit und belegte mit den meisten erzielten Toren den 5. Platz. Die Gesamtjahresplatzierung war ebenfalls mit dem 4. Platz die beste bisher. Nach Saisonende verließ Amaral, der „König von Tokio“, der 12 Jahre lang das Herzstück des Teams war, den Verein, womit ein Kapitel der Vereinsgeschichte zu Ende ging.

Im Jahr 2004 verfolgte das Team mit dem Slogan „Angriff, Angriffstheater, Angriffsfussball“ eine noch offensivere Spielweise als zuvor, doch aufgrund von Spielerabstellungen für die Qualifikation zur Fußball-Weltmeisterschaft in Deutschland und die Olympischen Spiele in Athen war die Mannschaft nicht vollständig, und in der J1-Liga erreichte man mit dem 8. Platz in der Gesamtwertung (6. Platz in der 1. Phase, 10. Platz in der 2. Phase) kein zufriedenstellendes Ergebnis. Dennoch schaffte es das Team im Yamazaki Nabisco Cup geschlossen bis ins Finale. Trotz eines Platzverweises in der ersten Halbzeit hielt man die 120 Minuten inklusive Verlängerung durch und gewann im Elfmeterschießen gegen die Urawa Reds. Damit sicherte sich der Klub seinen lang ersehnten ersten Titel.

Im Jahr 2005 wurde die Liga auf ein Einstufen-System umgestellt. Unter dem Motto „Angreifen und gewinnen“ führte das Team bis zur 4. Runde die Tabelle an, erlitt jedoch ab der 5. Runde mit einer Unentschiedenpause sieben Niederlagen in Folge. Am Ende belegte man den 10. Platz, und nach Saisonende wurde der Rücktritt von Trainer Hiromi HARA bekanntgegeben, der vier Jahre lang das Team leitete. Im Jahr 2006 übernahm mit Alexandre GALLO der erste ausländische Trainer des Vereins das Amt und trat unter dem Motto „Ousadia – Vertrauen, Mut, Herausforderung“ mit einer neuen Spielweise an. Doch aufgrund der langen Unterbrechung durch die WM in Deutschland und des ungewöhnlichen Spielplans konnte das Team nicht in Form kommen, sodass GALLO im August entlassen wurde. Ab der 18. Runde übergab man die Leitung der ersten Mannschaft an Hisao KURAMATA, der zuvor Trainer der FC Tokyo U-18 war. Trotz dieser Maßnahme endete die Saison mit der schlechtesten Platzierung der Vereinsgeschichte auf Rang 13, unter anderem wegen einer Serie von sechs Niederlagen ab der 20. Runde. Für die Saison 2007, in der man einen Neuanfang wagen wollte, kehrte Hiromi HARA als Trainer zurück und stellte das Motto „It's Our Time – Der blaue Sturm, die rote Flut“ auf. Nach einer Niederlage im Eröffnungsspiel der Liga setzte sich jedoch eine schwierige Phase mit weiteren Niederlagen fort. Der Neuzugang Wanchope (ehemaliger costa-ricanischer Nationalspieler) erzielte bis zur 11. Runde zwei Tore, konnte jedoch nicht die erhofften Ergebnisse liefern und verließ das Team Ende Juni. Die Saison 2007 beendete FC Tokyo in der J1-Liga auf dem 12. Platz, ohne wirklich in Fahrt zu kommen.