O Fluminense foi fundado no dia 1º de janeiro de 1941,por um grupo de jovens feirenses, que eram torcedores do Fluminense do Rio de Janeiro. A paixão era tanta que as cores eram similares as do homônimo carioca. O seu primeiro presidente foi Wilson da Costa Falcão e a diretoria era composta por nomes como Osvaldo Coelho Torres (vice-presidente); Laudelino Lacerda Pedreira, Otto Emanuel de Carvalho (secretários); Ariston Carvalho (diretor-técnico); Simonidas Carneiro (assistente); Fernando Garcia (diretor de sede); Colbert Martins (orador);Adroaldo Dórea, Alberto Oliveira e Valter Mendonça (médicos) e Humberto Luiz Portela e João da Costa Falcão (advogados).A primeira escalação, ainda como amadores, era formada por Newton (goleiro), Chico (lateral-direito), Zé Barros (zagueiro central), Brasilton (volante), Bianchi (volante), Tuta (lateral-esquerdo), Nogueira (ponta-direita), Heitor (meia-direita), Pamponet (centroavante), Tó (meia-esquerda) e Carlito (ponta-esquerda). Newton ainda se tornou prefeito da cidade em 1970.

A equipe se filiou à Liga Feirense em 1944 e, após três anos de filiação, o Touro do Sertão, como é conhecido o clube, conquistou o primeiro de quatro títulos amadores. As outras conquistas vieram em 1949, 1950 e 1953. Em 1953 o troféu de tricampeão foi recebido, já que o campeonato não foi disputado em 1951 e 1952.

Em 1954 aconteceu o primeiro grande passo na história do clube. Convidado pela Federação Baiana de Futebol, o Fluminense de Feira se tornou profissional e em 6 de junho do mesmo ano empatou com o Vitória no estádio da Fonte Nova por 1 a 1 em sua estréia. O gol da equipe foi marcado por Alfredo.

Durantes 13 anos o Flu foi o único time do interior a participar da primeira divisão do Campeonato Baiano. Nesse período conquistou o vice-campeonato em 1956, perdendo a final para o Bahia, mas sete anos depois o título finalmente veio em cima do Tricolor baiano. A partir de 1967, outros clubes do interior, como o seu vizinho Bahia de Feira, juntaram-se ao Fluminense e aos grandes da capital para disputar a primeira divisão. Depois da regionalização do campeonato, o Touro do Sertão ainda faturou a taça em 1969 com uma rodada de antecipação, batendo o Vitória por 1 a 0. Esse título foi o último conquistado por uma equipe do interior até o ano de 2006, quando o Colo-Colo de Ilhéus ficou com a taça.

Mascote

O mascote oficial do Fluminense de Feira de Santana é o touro, símbolo da força e do poder que o clube possui. É por meio de seu mascote que o Flu ganhou o apelido pelo qual é conhecido, Touro do Sertão.