Victor Lemonte Wooten cresceu em uma família militar, sendo o mais novo de 5 irmãos. Nascido em Idaho, ele viveu no Hawaii e na Califórnia antes de sua família se instalar em Newsport News, Virgínia. Todos os seus irmãos tocavam instrumentos musicais e cantavam, e, na época que Victor tinha 3 anos, seu irmão mais velho Regi começou a lhe ensinar a tocar baixo. Não importava, todavia, que o braço do instrumento e os trastes do baixo fossem grandes demais para as mãos de um garoto de 3 anos de idade. "Nesta idade você não pensa: ‘Eu não posso fazer isso, porque eu sou jovem demais", ele diz. "Todo mundo a minha volta estava fazendo música, então, eu nem tinha pensado, eu apenas fiz. Eu tenho o mesmo tipo de abordagem para tudo que eu faço. Eu não me preocupo se há um mercado para isso, eu apenas coloco a minha mente naquela tarefa e faço o melhor que eu posso. Uma das grandes lições que meus pais me ensinaram é que desde que suas motivações e razões estejam certas, você pode fazer quase tudo que você quiser".
Victor fez sua estréia profissional no palco quando tinha 5 anos no "The Wootens", a banda de cinco irmãos que tocavam os sucessos da rádio do dia – Sly & the Family Stone, War, James Brown, Motown, Curtis Mayfield – em um centro de recreação de danças. No ano seguinte, eles foram abrindo turnês de concerto pata Curtis Mayfield e War. E eles passaram vários anos tocando músicas e afinando suas habilidades no parque temático Busch Gardens em Williamsburg, Virgínia.
"Nesta época eu tinha 8 anos e nós nos considerávamos profissionais de temporadas. A rotina era: acordar, ir para a escola, ir para casa e fazer o dever de casa, tirava uma soneca, e então ir fazer uma apresentação das 10 da noite às 2 da madrugada. Em muitos lugares, nós nem podíamos deixar o palco, porque o lugar servia álcool e nós éramos menores. Era uma época boa para crescer, porque em qualquer lugar hoje você tem samplers e seqüenciadores para copiar tudo, antes se nós escutássemos sons em uma gravação, nós encontrávamos maneiras de fazê-lo ao vivo com o quê nós tínhamos".
Os "The Wootens" gravaram um álbum para a Arista Records em 1985 e aprenderam os altos e baixos da indústria das gravadoras por suas próprias experiências. Dois irmãos tocaram no álbum de estréia de Whitney Houston. Hoje, Joseph é o tecladista na "Steve Miller Band", Rudy é um saxofonista na Virgínia, e Regi toca guitarra e dá aulas em Nashville.
Em 1988, Victor se mudou para sua casa atual, em Nashville, para tocar em uma banda de rock. No ano seguinte, ele conheceu o ás do banjo Béla Flack da "News Grass Revival", o qual precisava juntar uma banda de jazz, rápido, para fazer a "Lonesome Pine Special", um especial de televisão. Victor e seu irmão baterista Roy (Future Man) tornaram-se a seção de ritmo, com Howard Levy nos teclados e gaita, e a "Fleckstones" nascia. Não havia precedentes para a "Fleckstones", uma banda de bluegrass com banjo e baixo elétricos e bateria sintetizada. "Nós apenas estalávamos", recorda Wooten. Rapidamente Fleck disse adeus à "New Grass Revival", e a "Fleckstones" tem estado ocupada desde então, embarcando um álbum no "Número 1" da Billboard, e pegando 4 nomeações para o Grammy Award.
Desde que Levy deixou a banda, no final de 1992, a "Fleckstones" tem continuado como um trio com convidados especiais tocando, o que indicava o quão estilisticamente a banda era livre: Branford Marsalis, Paul McCandless, Bruce Hornsby, Grover Washington Jr., o baterista de aço Andy Narell, e Chick Corea.
Em 1997, eles ganharam o Grammy de "Best Pop Instrumental Performance" por "The Sinister Minister" do seu CD "Live Art". Gravaram ao vivo em 1995, a trilha tem participação dos convidados especiais Howard Levy, Sam Bush, e Paul McCandless.
Enquanto Victor pode nomear dúzias de baixistas que o tem influenciado – de Bootsy Collins e Larry Graham a Stanley Clarke e James Jamerson da Motown -, "acima de tudo, isto é sobre música. Baixo é apenas meu modo de tocar música".
