Bloque representativo forjado a causa cívica del empeño y orden dictaminado por ciudadanos y comerciantes ingleses decimonónicos de la órbita de Salvador, cimentando lícitas campañas regulares abocadas a sostener o fortalecer la propia división formadora inferior del fútbol.
La institución se fundó el 13 de mayo de 1899 bajo la denominación original de Club de Cricket Victoria, gestada por iniciativa de los hermanos Artur y Eugênio Borges y un grupo de jóvenes provenientes de familias tradicionales tras retornar de estudios en Inglaterra. Establecieron su base en el barrio Campo Grande de Salvador, orientando la actividad fundacional exclusivamente al críquet. El 22 de mayo de 1901 disputaron su primer partido documentado de fútbol oficial obteniendo una victoria de 3-2 ante la tripulación de navíos ingleses anclados en el puerto. El año 1902 oficializó la modificación estatutaria del nombre a Sport Club Victoria para incorporar disciplinas atléticas diversas y asentaron permanentemente el uso de sus colores rojinegros institucionales.
El club participó como fundador en la creación de la primera liga oficial de fútbol estatal y conquistó el Campeonato Baiano de 1908 registrando la estadística invicta de seis victorias, definiendo su primacía sobre instituciones como São Salvador y Sport Club Bahia. En el torneo reglamentario de 1909 concretaron el bicampeonato tras revalidar su posición en lo alto de la tabla. Después de estos títulos tempranos, las imposiciones directivas centradas estrictamente en mantener un estatus de amateurismo produjeron una prolongada sequía de títulos institucionales frente a la profesionalización paulatina de sus rivales y del fútbol general local.
El equipo se adjudicó la edición 1953 del Campeonato Baiano superando en la fase de decisión a Botafogo de Bahía para cortar administrativamente una sequía deportiva de 44 años sin torneos de primera división oficial. Años más tarde, el proyecto de consolidación del departamento de fútbol se materializó formalmente con la inauguración del Estádio Manoel Barradas (conocido de manera corriente como Barradão). El recinto abrió sus operaciones el 11 de noviembre de 1986 albergando un partido de habilitación contra Santos Futebol Clube que finalizó en un empate numérico de 1-1, partido en el cual el jugador Dino anotó el primer gol oficial refrendado en los registros del campo deportivo.
Bajo la dirección táctica del entrenador Fito Neves, el equipo logró alcanzar la fase final absoluta del Campeonato Brasileño de 1993, convirtiéndose en el primer club del estado en llegar a esta instancia decisiva. Tras eliminar escalonadamente a equipos como Corinthians, Santos y Flamengo en grupos de cuadrangulares, se enfrentaron en las series finales contra Palmeiras acarreando dos derrotas de 1-0 el 12 de diciembre y 2-0 el 19 de diciembre. Este ciclo consolidó operativamente la capacidad formadora del club introduciendo talentos promovidos desde las divisiones juveniles (catalogados localmente como 'crias do Leão'), dotando a su nómina titular con el arquero Dida, el mediocampista Vampeta y el delantero Alex Alves.
El elenco matriculó su participación más larga en torneos de llaves eliminatorias del país alcanzando la final íntegra de la Copa do Brasil 2010, fase a la que accedió tras superar mecánicamente a Corinthians Alagoano, Náutico, Goiás, Vasco da Gama y Atlético Goianiense. La resolución del campeonato computó una derrota 2-0 registrada la noche del 28 de julio frente a Santos en São Paulo. En el duelo de validación final disputado como locales el 4 de agosto de 2010 frente a 34.111 personas en el Barradão, Vitória registró un triunfo arrojando el parcial de 2-1 mediante goles de Wallace a los 57 minutos y Júnior a los 77 minutos, resultando aritméticamente inoperante para el conteo global que coronó el título a favor del club paulista.