Member Nick Carter was unable to sing on the recording of the song, as his voice was changing due to puberty at the time. The song was recorded at Cheiron Studios in Sweden during a week in June 1995 with writers and producers Max Martin and Denniz Pop. The band was brought over for a week to record only this song; however, they finished unexpectedly in just two days. As a result, Martin and Pop suggested another song for the band to record, "Quit Playing Games (with My Heart)".
The band's first music video was filmed on August 19, 1995 in Orlando, Florida, was directed by Lionel C. Martin, and is prefaced by a false radio interview introduction. The video itself features the band singing at a gym, outdoors at a park area, and in a studio space, as well as dancing onstage at a club, playing basketball, washing a Jeep, and playing at an arcade pool hall. The video features a brief appearance by Lou Pearlman. Brian Littrell's then girlfriend Samantha Stonebraker and Samantha's brother Steven Stonebraker appear in the Jeep/Basketball scene, while AJ McLean's then girlfriend Marissa Jackson appears as the Money collector during the Pool game in the video.
"We've Got It Goin' On" was first released in the U.S. but had only limited success. It peaked #69 at Billboard Hot 100 and spent 20 weeks charting. After that the single was released over Europe and it gained popularity and the Backstreet Boys topped the European charts.