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 consisted of a series of university and nightclub gigs, where they performed a set list consisting of a selection of songs from their Greatest Hits album. This had 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.
After O'Meara, Cattermole and McIntosh reunited, rumours persisted that S Club would fully reunite (with all seven members). Barrett re-joined the group for one performance in March 2014. In October 2014, it was confirmed that the original lineup would reunite for the first time in over a decade for BBC Children in Need.S Club 7 announced their plans for an arena reunion tour, promptly entitled Bring It All Back 2015, which toured the UK in May 2015.
In January 2014 Skua reformed with all original members. The members had not seen one another for almost 12 years then in early 2014 they made contact with each other via facebook and a meet up was organised soon after. They initially planned to release the material they had recorded in 2002 and have a jam. During the jam session guitarist Stevie K played a demo of the track that would become their first single, Falling and from there an entirely new album was written. On 9 October 2014, Skua performed to a packed crowd at the release of their first official album titled Kneel. The band plan to play more shows in support of the release.
Cattermole and Hannah Spearritt first met each other when Paul was 17 years old and Hannah was 14 years old, when they were both members of the National Youth Music Theatre in 1994, and they both co-starred in show production called Pendragon. In 1999, Cattermole and Spearritt became band members, a part of a seven piece pop group called S Club 7 in which they became good friends. However, in May 2001, Paul and Hannah's friendship developed into romantic relationship, they kept their relationship a secret for six months. Later in the same year, they make a public announcement to confirm that they were an item. Their S Club bandmates supported their new relationship status and released a statement. Following Cattermole departure from S Club 7 in 2002 and when S Club announced in 2003 that they were to disband, the couple continued to date. However, in early 2006, Cattermole and Spearritt's five-years romantic relationship was over and afterwards they stayed in touch and remained friends. In 2014, Cattermole and Spearritt reunited with their S Club 7 bandmates for the reunion, during a television interview on ITV's Loose Women show, they were asked by the Loose Women presenters if it was awkward for them to be working together after their previous relationship together. Spearritt answered joking "That's why we're sitting so far apart. It's really awkward!" While Paul replied that “it was in fact great to be together again. No, it's great to be back together, working together with everyone." In June 2015, it was confirmed that Cattermole and Spearritt have started a romantic relationship again.