A Brisbane junior, Protheroe started his rugby league career in 1990 playing for QRL side Redcliffe Dolphins in the Brisbane competition. In 1991, Protheroe along with Redcliffe coach Mark Murray were signed by the Eastern Suburbs Roosters. Protheroe made his first grade debut in his sides' 16-10 loss to arch rivals the South Sydney Rabbitohs at the Sydney Football Stadium in the opening round of the 1991 season. Despite a poor season from the Roosters in which they finished in 11th position, Protheroe had a brilliant rookie season, he played in 20 of his sides' 22 games and scored 7 tries. Protheroe narrowly missed out on winning the Dally M award for Rookie of the Year. Instead Will Robinson of the Balmain Tigers won the award. More success followed Protheroe in the 1992 season, despite the Roosters narrowly missing out on finals qualification for the first time since 1987, finishing in 6th position, Protheroe starred, playing in all 22 games and scoring 6 tries. For his efforts, Protheroe was considered for the Queensland side in the 1992 State of Origin series, however Protheroe ultimately missed out on selection when Adrian Brunker and Michael Hancock were instead chosen as the wingers. Protheroe played his first match in the forwards when he was chosen at second-row in round 17 of the 1993 season, he would play most of his later career in this position. After disappointing seasons in 1993, 1994, and 1995 in which the Roosters finished 8th, 14th, and 9th respectively, Protheroe decided to leave the Roosters at the end of the 1995 season and returned to Brisbane. In 1996, after five seasons in Sydney with the Roosters, Protheroe returned to Brisbane, this time to play for the South Queensland Crushers. He along with fellow Roosters Nigel Gaffey, Jason Hudson, Graham Mackay and Clinton O'Brien joined the ill-fated Crushers. Despite having a relatively strong playing roster which included these players as well as former Origin players Terry Cook, Trevor Gillmeister and Tony Hearn, the Crushers finished with the wooden spoon in both the 1996 and 1997 seasons. With the demise of the Crushers at the end of the 1997 season, Protheroe decided to retire from playing. He finished his career having played 123 games and scoring 33 tries.
