Born in Winter Haven, Florida, Gaines unsuccessfully tried other sports during his teen-age years but turned to swimming as a Winter Haven High School junior where he improved quickly and was offered a swimming scholarship to Auburn University. At Auburn he became a five-time NCAA champion under the training of former Auburn head swimming coach Richard Quick. From 1978 to 1984, Gaines set ten world records, and had the United States not boycotted the 1980 Summer Olympics in Moscow, he would have been a favorite to win multiple medals at the event. After graduating from Auburn in 1981, he stopped swimming for several months, thinking he had missed his opportunity to be an Olympic medalist, but was urged to resume swimming by his father. When Gaines qualified at the 1984 Olympic trials, his times were not particularly impressive and he was not expected to place at the 1984 Summer Olympics in Los Angeles, California. He won the 100 meter freestyle off a very good start and swam the anchor leg for both the winning U.S. teams in the 4×100-meter freestyle relay and 4×100-meter medley relay.
In August 1991, Gaines was temporarily paralyzed with Guillain-Barré syndrome. After a two-month hospitalization, he experienced a surprising full recovery attributed largely to his superb physical condition as a competitive swimmer. He eventually regained world-class times and, at the age of 35, became the oldest swimmer to qualify for the trials for the 1996 Summer Olympics. Ultimately, he chose not to compete in the trials for the 1996 Olympics but instead continued his career as a television commentator, covering swimming for NBC at the Games.
Gaines was Outreach Director for the Alabama Sports Hall of Fame in Birmingham, Alabama from 1997 until 2003 when he moved to Colorado Springs, Colorado to become the Chief Fund-raising and Alumni Officer for USA Swimming. In December 2007, Gaines became a spokesperson for LIMU, The Company, a Direct Sales Company that manufactures LIMU ORIGINAL, BLU FROG, LIMU LEAN, and LIMU ORIGINAL SHOTS.
Gaines still holds masters long course world records in several freestyle events. At the 2011 Short Course Masters Nationals, Gaines broke his own national record in the 50–54 division 50 yard freestyle (21.36), notable in that he did the swim without the use of a technical suit (now banned). On July 16, 2011, Gaines broke the 50–54 Age Group record in the long course 100m freestyle with a time of 54.6. Gaines currently resides in Lake Mary, Florida where he is Executive Director of Rowdy's Kidz, a charitable program sponsored by LIMU, The Company. His wife, Judy, and he have four daughters: Emily, Madison, Savanna and Isabelle.