Cattermole became a member of S Club 7 after a series of auditions, along with members Tina Barrett, Jon Lee, Bradley McIntosh, Jo O'Meara, Hannah Spearritt and Rachel Stevens in 1999. During five years they released four number one singles and one number one album. They also had a series of TV shows, which were: Miami 7, L.A. 7, Hollywood 7 and Viva S Club. In March 2002, Paul Cattermole told The Sun newspaper that it was time for him to "move on" from the group and he wanted to go back to his "rock roots", which heralded back to the time he was part of a nu metal band formed with his old school friends. Talking about his former musical venture three months before he left S Club 7, Cattermole described the band—who had been called Skua—as having a "Limp Bizkit vibe" as well as comparing their style to Rage Against the Machine. Cattermole's resignation came as Skua had decided to reform, and he found it a perfect time to make the transition back from pop to rock as S Club 7's record contracts were up for renewal. Cattermole stayed with the band until June 2002, featuring in four out of thirteen episodes of the group's final television series, Viva S Club, and performing his final concert with the group for Party at the Palace, which was part of Queen Elizabeth II'sGolden Jubilee celebrations.
After a five-year split, it was announced in October 2008 that O'Meara, Cattermole, and McIntosh were to perform a mini-reunion tour. The tour consists of a series of university and nightclub gigs, where they perform a set list consisting of a selection of songs from their Greatest Hits album. They has been performing in various nightclubs, universities and Butlins holiday camps around the United Kingdom. Cattermole sang with his own band at a charity concert called 'The Sounds of Summer' at 'The Lord Taverners' club in London on 27 July 2011.