He signed his first deal in 1998 with Tommy Boy Records, the label offering him $1 million compared to Dr. Dre's Aftermath Entertainment, who offered him $250,000 and unlimited beats—what Royce expressed as his "biggest regret" in a March 2016 interview with "Complex". After Tommy Boy Records shut down, he signed a deal with Columbia and Game Recordings where he started recording an album called "Rock City", referring to Detroit's former status as home to Motown Records. When the project was heavily bootlegged, Royce left the label for Koch to re-record some of the album, eventually releasing it in 2002 as "Rock City (Version 2.0)". While the album did not sell very well, the DJ Premier-produced single "Boom" gained Royce some underground recognition and eventually resulted in the two working together more closely.