Stacey's first experience of performing music was singing in a church choir at a young age. In 2001, while working at a London branch of NatWest, he auditioned to become a member of Hear'Say, the pop group that was being formed from the reality television programme Popstars. He impressed the show's judges with a rendition of "Angels" by Robbie Williams and progressed on to the "boot camp" stage of the competition. During the second day of boot camp, Stacey opted to perform a hymn rather than a pop song for the judges. Nigel Lythgoe, one of the show's judges, informed him that the final band was obviously not going to perform hymns and that, at that stage in the competition, the judges were looking for small reasons such as this to eliminate contestants. However, Stacey's part in a group performance of "Monday, Monday" by The Mamas & the Papas was seen as sufficient enough to keep him in the competition for another day.
Stacey was ultimately eliminated from the Popstars competition on the fourth day of boot camp, with the show's judges saying that he was "more gospel-influenced and [they] were after something altogether more poppy". He originally intended to form a trio with Taz and Raymond, two other Popstars contestants who had been elimanted the same day as him. Within weeks of his elimination, Stacey was signed as a solo artist by Def Jam Recordings, who flew him to Los Angeles to write and record his debut single "My Girl My Girl" with production team Red Zone. He played alongside Hear'Say and fellow Popstars contestants Liberty at the 2001 Smash Hits tour in December, before releasing "My Girl My Girl" in March the next year. The single peaked at Number 26 on the UK Singles Chart, with Stacey's sound being favourably compared to that of fellow British R&B singer, Craig David. Stacey provided support at the final night of MTV's Five Night Stand in April and went on to support Destiny's Child on their UK tour in June.