He was also named the Grey Cup Most Valuable Canadian in 2006 and won the CFL's Most Outstanding Special Teams Award in 2011.

He also suited up briefly for the Vancouver 86ers for a preseason tournament (while in Grade 12 at Surrey BC's Queen Elizabeth Sr Sec.)

McCallum travelled to Scotland at 19 years of age to play professional soccer in the Scottish Third Division for clubs St. Mirren and Hamilton Academicals.

After being released, he had numerous short stints with the Ottawa Rough Riders, (1992–1993) during his time there he was a teammate of former NFL Washington Football Club Dexter Manley and former WWE wrestler Glenn Kulka, BC Lions (1993,1994, 2006–2014, 2016) and Saskatchewan Roughriders (1994-1995, 1996–2005, 2015).

McCallum once again travelled to Scotland to play professional sports, this time as the punter and placekicker for the Scottish Claymores of the World League, and was with the team when they won World Bowl 1996 at Murrayfield Stadium Sunday, June 23 where they beat the defending champions, Frankfurt Galaxy 32-27 in front of 38,982 fans.

Other notable players on the Claymores roster included former Denver Broncos wide receiver Yo Murphy, former NFL quarterback Jim Ballard, as well as Scotland Rugby Union legend Gavin Hastings OBE.

[3] Prior to his spell in NFL Europe (1996) with the Scottish Claymores McCallum had been playing with the Riders, upon his return to Canada he resigned with the Saskatchewan Roughriders and tore his ACL early in the into the CFL season.

After recovering he returned to play for the club until 2000 at which time he left to sign with the Las Vegas Outlaws of the XFL for their 2001 football season.

The Roughriders went on to lose the game, and outraged fans vandalized McCallum's northwest Regina home with eggs, dumped manure on his neighbour's property, and uttered death threats to his family.

On the comedy show This Hour Has 22 Minutes, Shaun Majumder (playing a Roughriders GM) apologized for calling McCallum "a bum who could be out-kicked by a goat missing a leg".

[9] On October 8, 2011 at BC Place in Vancouver, Paul set the record, with 30, for the most all-time consecutive field goals made in the CFL, breaking the previous mark of 28 held by Dave Ridgway.

Rob Vanstone Sports Editor Regina Leader-Post[16] On July 1, 2015, McCallum signed with the Saskatchewan Roughriders.