A Série C do Brasileirão chegou em 2004 com o habitual "efeito sanfona" em seu formato. Os 93 participantes do ano anterior foram reduzidos para 60 equipes, todas qualificadas pelo desempenho nos campeonatos estaduais ou pelo rebaixamento da Série B na temporada anterior. A exemplo de 2003, a grande sensação do torneio voltou a emergir do interior paulista: o União Barbarense atingiu o momento mais glorioso de sua história ao erguer o mais importante troféu de sua trajetória.
Na etapa inicial, os clubes foram distribuídos em 16 grupos. O União Barbarense iniciou sua jornada no Grupo 14. A estreia ocorreu em São José do Rio Preto contra o América-SP e terminou com triunfo alvinegro por 1 a 0. Nos dois compromissos seguintes sob seus domínios, no Estádio Antônio Guimarães, o empatou duas vezes em 0 a 0, contra Rio Branco-SP e União São João.
Os tropeços em casa foram rapidamente compensados com duas vitórias como visitante: 1 a 0 sobre o União São João em Araras e 3 a 2 diante do Rio Branco em Americana. Encerrando a fase de grupos, o Leão da 13 derrotou o América-SP por 2 a 1 em Santa Bárbara d'Oeste. Com 14 pontos conquistados, o time alvinegro garantiu a liderança do grupo.
A segunda fase reservou um duelo paulista contra a Portuguesa Santista. Na partida de ida, em Santos, o União sofreu um revés por 1 a 0. A resposta na volta foi avassaladora: uma goleada por 4 a 1 no Antônio Guimarães assegurou a classificação. Nas oitavas de final, a equipe reencontrou o Rio Branco-SP. Com superioridade, o Leão avançou com duas vitórias, por 2 a 0 fora e por 3 a 1 em casa.
Nas quartas de final, valendo a vaga para a fase decisiva, o adversário foi o Iraty. O time alvinegro fez valer seu favoritismo ao vencer o confronto de ida no interior do Paraná por 1 a 0 e administrar a vantagem no jogo de volta em Santa Bárbara d'Oeste com um empate em 1 a 1.
O quadrangular final reuniu União Barbarense, Americano, Limoeiro e Gama. A caminhada começou com o pé direito em solo fluminense, na vitória por 1 a 0 sobre o Americano em Campos dos Goytacazes. De volta ao Antônio Guimarães, o Leão engatou mais dois triunfos: 3 a 2 sobre o Limoeiro e 2 a 1 contra o Gama. Com um desempenho impecável, o União Barbarense assegurou o acesso antecipado à Série B logo na quarta rodada, ao atropelar o Gama por 4 a 1 em pleno Distrito Federal.
O título nacional veio na penúltima partida: mesmo sofrendo uma derrota por 2 a 0 para o Limoeiro em Fortaleza, o alvinegro não pôde mais ser alcançado na tabela, favorecido pelo empate entre Gama e Americano no outro jogo. A coroação da campanha ocorreu na rodada de encerramento, com uma vitória por 1 a 0 sobre o Americano perante uma torcida em festa em Santa Bárbara d'Oeste.
