A fase negra nas Laranjeiras ia passando aos poucos. Ao ganhar a série C em 1999, o Fluminense se preparava para retornar à segunda divisão, e lutar para enfim voltar ao lugar da onde jamais deveria ter saído. O clube voltou a ser dirigido com seriedade, e iria encarar com dignidade a série B. No entanto, no ano de 1999, uma grande confusão perturbou o cenário do futebol brasileiro naquele ano. O caso envolvendo os rebaixados da série A para a B, que envolvia cálculos e ainda o caso Sandro Hiroshi, atleta do São Paulo envolvido em um caso de adultério de idade, acabou causando um grande tumulto entre o STJD, a CBF e o Clube dos Treze, já que algumas equipes reclamaram de que haviam sido prejudicadas pelas punições e regulamento. Com isso, o Campeonato Brasileiro de 2000 foi suspenso.
Sem um campeonato para disputar, o Clube dos Treze resolveu entrar na parada e remontar o Brasileirão. Pegou todas as equipes e dividiu em quatro módulos, e assim como em 1987, as organizou por importância, ou seja, os mais importantes para o futebol brasileiro ficaram no primeiro módulo (série A), as de média importância na segunda e terceira, e as de menor expressão, na última. O módulo principal fora chamado de módulo azul, os demais, respectivamente de amarelo, verde e branco. Os melhores qualificados dos módulos amarelo e azul se enfrentariam em uma fase final e disputariam o título brasileiro daquela edição.
O Fluminense, mesmo em má fase, foi chamado para jogar no módulo principal, devido a sua tradição diante o futebol brasileiro. Foi assim que o Tricolor retornou legalmente à primeira divisão, sem nenhum esquema ou manipulação. Qualquer outra coisa dita que não seja isso, é pura mentira.
A prova da força do Fluminense, é que ele terminou em terceiro e classificado no módulo azul. Certas equipes, como aquela equipe da Gávea, sequer conseguiram se classificar para a fase seguinte. Com 42 pontos, ficou à apenas três do campeão Cruzeiro, com quem avançou junto as outras 10 equipes (os 12 melhores passavam) para enfrentar os oito melhores de cada um dos dois grupos do módulo amarelo.
No entanto, logo nas oitavas-de-final, o Fluminense foi derrotado pelo futuro vice-campeão São Caetano, empatando a primeira partida no Anacleto Campanella por 3x3, e perdendo no Maracanã por 1x0, dando adeus à competição, mas mantendo-se dignamente na série A.
Os dias nas Laranjeiras enfim voltavam a ser de Sol. O Fluminense estava realmente de volta, e as vésperas de um marco importante na sua história. No ano de 2002 o Tricolor completaria 100 anos, e com isso, o objetivo de 2001 era conseguir uma vaga na Copa Libertadores. O clube seguiu firme nesse objetivo. Conseguiu o terceiro lugar na primeira fase, e seguiu em frente. Na fase eliminatória, onde as partidas eram únicas, deixou pra trás a Ponte Preta pelo placar de 3x2 no Maracanã. Na semi-final, o Flu teve que ir até a Arena da Baixada enfrentar o forte Atlético-PR. Se vencesse, cravaria ser retorna à competição continental após 17 anos. O Flu saiu na frente, com o lendário Magno Alves no fim do primeiro tempo. Na segunda etapa, o jogo pegou fogo. A estrela do artilheiro Alex Mineiro brilhou forte, e o Atlético-PR virou o jogo com dois gols, aos 4 e 24. No entanto, se lá tinha Alex, aqui tinha Magnata, que empatou aos 29. O jogo seguiu pegado, mas a pressão da torcida atleticana fez a diferença, e aos 44 minutos, Alex Mineiro concretizou a classificação rubro-negra para a final, eliminando o Fluminense.
Sem a Libertadores, o Tricolor teve que ir para o seu centenário visando a conquista do Brasileirão, e investiu bem para isso. O clube, com a ajuda da Unimed, que entrará em 1999, fez sua primeira grande contratação na década: Romário. Sua estréia foi diante de 70 mil Tricolores alucinados no Maracanã, que viram uma partida inesquecível contra o Cruzeiro. O Baixinho fez dois, Magno Alves fez outro, assim como Fernado Diniz e Beto, que marcaram os gols da goleada por 5x1, que foi a primeira partida daquele Brasileirão, que teve o Tricolor oscilando entre altos e baixos, mas mesmo assim, conseguindo a classificação para a fase final.
Contra o São Caetano, vitória por 3x0 e derrota por 2x0, garantindo o Flu na fase seguinte. A semi-final, contra o Corinthians, teve no Maracanã 1x0, com gol de Romário, seu 16º na competição. No jogo de volta, o alvinegro venceu por 3x2 e passou por conta da sua melhor campanha na fase inicial.
No entanto, o ano de 2002 também foi de alegrias. Antes da disputa do Campeonato Brasileiro, o Flu venceu seu 29º estadual, ao derrotar o Americano na final, vencendo por 2x0 e 3x1 as partidas finais, e sagrando-se campeão no seus centenário. Além da conquista, o Flu venceu a sua partida comemorativa, contra o Deportivo Toluca, do México, erguendo a taça do Centenário, ao derrotar os mexicanos por 3x1 no Maracanã.
No ano seguinte, o ano começa com um campeonato carioca diferente. Sem a Taça Rio, os clubes disputam apenas a Taça Guanabara, sendo disputado em turno único com todos enfrentando todos. O Fluminense realizou uma boa campanha, terminando em terceiro e se classificando para a semi-final, onde derrota o Flamengo por 1x0 no primeiro jogo e goleia por 4x0 no segundo, seguindo para a final contra o Vasco. No entanto, dessa vez o time da colina não foi vice, pois venceu os dois jogos por 2x1 e sagrou-se campeão carioca pela última vez até os dias de hoje.
O resto do ano não é muito animador para os Tricolores. Além da eliminação nas oitavas-de-finais da Copa do Brasil para o Sport, o Flu realizou um mal Brasileirão e ficou em 19º, no velho campeonato de 24 equipes. Os mesmo vale para 2004, que foi mais um mal ano nas Laranjeiras, sem títulos e de poucas aspirações.
Já 2005 o Tricolor pode-se orgulhar-se novamente da equipe. Começa com a heroica conquista do Cariocão, com o milagre de Antônio Carlos, marcando um gol de nuca aos 43 minutos do segundo tempo, cravando o 3x1 no placar do Maracanã e dando o título sobre o Volta Redonda. A conquista embala o Flu pela Copa do Brasil, que passa por Campinense-PB, Esportivo-RS, Grêmio, Treze-PB, Ceará e para no Paulista, que surge como uma grande zebra e segura o Flu em São Januário, marcando para sempre o estádio como "proibido para Tricolores".
A perda da Copa do Brasil não desanimou a equipe comandada por Abel Braga. O técnico Tricolor colocou a equipe na luta pelo título, mas no final do campeonato, black-out. Até hoje procuramos explicações para o apagão Tricolor na reta final. Precisando de apenas uma vitória nos últimos cinco jogos para garantir sua vaga na Libertadores, o Fluminense consegue perder todas, inclusive para o Palmeiras, na rodada final, por 3x2, de virada.
Se em competições nacionais ficou no quase, em internacionais também. Depois de deixar o santos e Banfield pra trás na Copa Sul-Americana, o Tricolor foi eliminado pela Universidad Católica, após vencer por 2x1 no Rio, mas perder por 2x0 no Chile. A equipe chilena teve com destaque um certo argentino chamado Darío Conca... enfim, alguns anos mais tarde voltaríamos a ouvir falar dele.
O ano de 2006 não foi dos melhores, muito pelo contrário. O Fluminense amargou um ano de decepções em todas as competições que disputou, e quase foi rebaixado no Brasileirão, mas safou-se na reta final.
Já 2007... ah, enfim o brilho de uma verdadeira conquista. Mas preferi deixar esse capítulo para depois, pois marca o início de uma nova fase, precedendo o Time de Guerreiros.
