El Victoria Club de Fútbol fue fundado en febrero de 1943 en el barrio de Santa Lucía y se ha caracterizado siempre por el cuidado y gusto de sus futbolistas, pues es uno de los clubes de la ciudad que más futbolistas ha relanzado a la elite del fútbol nacional. En este aspecto hay que recordar a futbolistas de la talla de Amancio Amaro, ex jugador del Real Madrid, Real Club Deportivo y de la selección española; Jaime Blanco (RC Deportivo, Real Madrid, Oviedo, Befis y Hércules); Moncho Parada (RC Deportivo, Real Madrid y Rayo Vallecano, entre otros); Pepiño Sánchez (Málaga, Granada, Ceuta) y otros muchos.
A nivel deportivo se debe destacar la temporada 1971-72 en la que el Victoria CF consiguió el título de campeón de Primera División y posteriormente el de Campeón Gallega de Micionados. En esta competición tuvo que eliminar al Iris de Magoy (Lugo), Maniños (Ferrol) y Noya, derrotando en la final al Juventud de Cambados, que había ascendido a Tercera División, por 2-0.
Como logros más recientes se deben señalar el Campeonato Gallego y Subcampeonato de Copa, ambos en categoría cadete, alcanzados durante la temporada 1996-97; el subcampeonato Gallego de Fútbol-7 en categoría alevín en la temporada 1998-99; y el ascenso logrado a la Liga Nacional Juvenil en la temporada 1999-00, así como los ascenso a la División de Honor de categoría cadete (como campeón de la Liga Gallega), en la temporada 2000-01 y a la Liga Gallega infantil en esta misma campaña.
Es conveniente recordar otros logros, como los campeonatos de Segunda División en las temporadas 1953-54, 58-59, 68-69 y 77-78, también es digno de resaltar la temporada 1996-97 en la que el equipo aficionado se proclamó campeón del Grupo I de Tercera Regional alcanzando el consiguiente ascenso a Segunda Regional, categoría en la que milita.
La junta directiva ha asumido el proyecto de mimar a todas sus categorías, aunque haciendo hincapié en su propia cantera, y de relanzar el club, tanto deportiva como socialmente. Este trabajo se refleja con los datos del número de jugadores que pertenecen al club y cuya cifra sobrepasa los 250.