Клубът е основан на [[13 май]] [[1899]] г. от братята Артур и Артемио Валенте, завърнали се след обучението си в Англия. На [[22 май]] [[1901]] г. Витория играе първия си мач срещу сборен отбор съставен от английски моряци. От тогаваОттогава до момента клуба не е променял клубните си цветове които са в червено, бяло и черно. Първият му официален мач е на [[13 септември]] [[1903]] г. в който Витория побеждава отбора на град [[Паулища]] с 2:0. През [[1908]] г., Витория печели първата от общо 25-те си титли от Кампеонато Баяно. През [[1994]] г. след изключително слаб сезон отбора изпада в бразилската втора дивизия. През [[1995]] г. клуба продължава с неубедителното си представяне като завършва на 17-то място и изпада в Трета дивизия. През следващата [[1996]] г. става вицешампион на Серия „Ц“ и печели промоция за втора дивизия. През [[1997]] г. Витория Баия се състезава в бразилската втора дивизия и след като завършва на 4-то място, се завръща в елитна.
