Em Atlanta 1996, competindo no revezamento 4x100 m junto com Gail Devers, Inger Miller e Gwen Torrence, ela conquistou a medalha de ouro da prova e tornou-se campeã olímpica. No ano seguinte, Gaines adicionou mais uma medalha de campeã mundial a seu cartel, novamente integrando o revezamento que conquistou o ouro no Mundial de Atenas 1997.[2]
Ela retornou aos Jogos Olímpicos em Sydney 2000, aos 30 anos, como única sobrevivente do revezamento campeão olímpico de 1996 e, ao lado das novas companheiras Marion Jones, Torri Edwards e Nanceen Perry, ficou com a medalha de bronze no 4x100 m. Sete anos depois, devido à confissão de Jones de que havia usado substâncias proibidas no período dos Jogos de Sydney, Gaines, Edwards e Perry foram intimadas pelo COI a devolverem suas medalhas de bronze ganhas junto com Jones. Depois de uma apelação das atletas - assim como das demais integrantes do revezamento 4x400 m, também integrado por Marion Jones em Sydney e que havia ganho o ouro - em julho de 2010 o Conselho Arbitral do Comitê Olímpico Internacional permitiu às atletas que elas mantivessem suas medalhas.[3]
