After winning the ABA Championship, Gaines would retire from playing basketball and start out as an assistant coach for the Long Beach Jam in their second year of existence. During the season, he would take over the head coach role there after their previous coach would accept a coaching role in the NBA. After the Jam's second season ended, it was announced that the Long Beach Jam would not play the next season due to their eventual move to Bakersfield in order to complete their transition to the NBA Development League. As a result, he would soon be an assistant coach for the Phoenix Mercury for the 2006 and 2007 seasons. On November 7, 2007, Gaines became the head coach of the Phoenix Mercury, replacing outgoing head coach Paul Westhead. Gaines had prior experience with Westhead's offense, having played for him at Loyola Marymount University and with the Nuggets. Gaines kept the same offense that Westhead employed, and in 2009, he directed the Mercury to their second WNBA title. Under Gaines' guidance, Diana Taurasi became the second player in WNBA history to win the regular season scoring title, the WNBA MVP Award, the WNBA Championship, and the WNBA Finals MVP Award in the same season. In November 2011, Gaines was promoted to general manager of the Mercury, taking over a position vacated by Ann Meyers-Drysdale. On August 8, 2013, the Phoenix Mercury announced that they had relieved Gaines of his duties as head coach and general manager, and named former University of Arizona and Grand Canyon University men's basketball head coachRuss Pennell as the team's interim head coach. Gaines would have his first coaching experience in the NBA with the Phoenix Suns as a player development coach, starting back in the 2010-11 season. In January 2013, Gaines was temporarily promoted to being an assistant head coach for the Phoenix Suns alongside Dan Panaggio after both Dan Majerle and Elston Turner would resign from their roles after the announcement of Lindsey Hunter being the team's interim head coach. He would then continue working under the organization throughout the rest of the 2012-13 NBA season until the Suns hired permanent replacement assistant head coaches to replace their old coaching staff, although Gaines would still work for the organization as a player development coach alongside Irving Roland during the 2013-14 and 2014-15 seasons. However, on July 30, 2015, Gaines would end up being promoted back as a full-time assistant coach for the Suns for the 2015-16 NBA season due to some changes with the coaching and player development staffs respectively. Gaines would also be considered a prime candidate for the interim coach tag for the Suns after head coach Jeff Hornacek was fired on February 1, 2016. However, after a generally awful season that was even worst then their 2012-13 season, Gaines would not have his contract renewed with the team. Before the start of the 2016-17 season, Gaines would reunite with head coach Jeff Hornacek and assistant coach Jerry Sichting as an assistant coach for the New York Knicks. Prior to the start of the 2018-19 season, the Detroit Pistons hired Gaines as a Coaching Consultant. Before the start of the 2019-20 season, Gaines was hired as an assistant coach with the Washington Wizards.
Personal life
Gaines' father is African-American and his mother is of Japanese descent.