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 as members of the National Youth Music Theatre in 1994. At the time Paul was 17 years old, and Hannah was 14. They appeared together in Pendragon. In 1999, Cattermole and Spearritt both were selected as band members of a seven member pop group named S Club 7, where they became good friends. In May 2001 the friendship developed into romantic relationship. They kept their relationship a secret for the first six months, waiting until November 2001 to make a public announcement. Their S Club bandmates were supportive of the relationship. Cattermole departed from the band in 2002 but the couple continued to date. S Club announced in 2003 that they were to disband. In early 2006 Cattermole and Spearritt's five year relationship ended. In 2014, Cattermole and Spearritt reunited with their S Club 7 bandmates for a reunion. During a television interview on ITV's Loose Women they were asked if it was awkward for them to be working together after their previous relationship together. Spearritt jokingly answered "That's why we're sitting so far apart. It's really awkward!" More seriously, Paul commented “No, it's great to be back together, working together with everyone." In June 2015 Cattermole and Spearritt started a romantic relationship again.