Fondato il 21 luglio 1902 da Oscar Cox, giovane figlio di un cittadino inglese vice-console d'Inghilterra in Ecuador, il Fluminense Football Club indossava, all'epoca, i colori grigio e bianco. Cox è uno dei principali responsabili dell'arrivo del calcio in Brasile. In diversi viaggi nella "Terra della Regina", ha sempre portato notizie, palloni, materiali sportivi. Ha anche giocato, è stato campione carioca del 1906, quando Fluminense era già verde, bianco e grená. Con problemi ad acquisire il tessuto grigio per l'uniforme originale, nel 1904 fu approvata la modifica, dando vita al Tricolore.
Pioniere, il Fluminense costruì il primo stadio di cemento in America Latina, lo Stadio Laranjeiras, che ospitò il Campionato Sudamericano per Squadre Nazionali, attualmente Copa América, e i Giochi Olimpici Latinoamericani, attualmente i Giochi Panamericani, e fu teatro del primo titolo rilevante della Nazionale Brasiliana.
Considerato il premio Nobel per lo sport, il Fluminense è l'unico club in America Latina che detiene la Coppa Olimpica nel 1949, oltre ad essere l'unica squadra di calcio al mondo ad avere il suo nome inciso sull'onore concesso dal Comitato Olimpico Internazionale per i servizi allo sport.
Era di Preguinho, uno degli idoli tricolori, il primo gol della Nazionale brasiliana nei Mondiali. Dopo Cox, molte stelle hanno indossato la maglia del Fluminense. Oltre a Preguinho, Pinheiro, Hércules, Escurinho, Waldo, Orlando Pingo de Ouro, Welfare, Ademir de Menezes, Rivellino, Altair, Jair Marinho, Gerson, Marcos Carneiro de Mendonça, Félix, Castilho, Carlos Alberto Torres, PC Caju, Pintinho, Branco, Didi, Ézio, Romerito, Assis, Washington, Renato Gaúcho, Tele Santana, Romário, Deco, Conca, tra gli altri, ha fatto la gioia della folla tricolore.
Quattro volte campione brasiliano, campione della Copa do Brasil e della Copa da Primeira Liga, e 31 volte campione dello Stato. Seconda classificata della Copa Libertadores e della Coppe Sudamericane.
Oltre alla sede di Laranjeiras e Maracanã, dove gioca le sue partite, Fluminense ha due centri di allenamento. Quello di Xerém, a Duque de Caxias, è incentrato sulle divisioni di base, e quello di Barra da Tijuca, nel calcio professionistico.