Nicholson comenzó su carrera como aprendiz en Doncaster Rovers y debutó profesionalmente en 1989 con el ex capitán de Escocia , Billy Bremner . Después de 4 años en Belle Vue, pasó a Hereford United , Torquay United y luego Scunthorpe United jugando más de 150 partidos de liga.
Habilidoso mediocampista del lado izquierdo, nunca alcanzó su potencial en Inglaterra y pasó a jugar profesionalmente en la S. League de Singapur con su ex compañero de Scunthorpe Stuart Young durante cuatro años y fue votado como el jugador del año de la S League del Straits Times en 1997. .
Jugó para Geylang United y Woodlands y actuó como testigo en el escándalo de amaño de partidos de 2000 cuando, después de ser atacado con un palo de hockey por el notorio Wilson Raj Perumal [1] junto con su compañero jugador de Woodlands Ivica Raguz , dos jugadores de la S League, El portero alemán Lutz Pfannenstiel y el defensa australiano Mirko Jurilj fueron encarcelados por presunta amaño de partidos. Nicholson había sido arrestado originalmente junto con otros jugadores británicos de Geylang United , Billy Bone y Brian Bothwell . [2]
No se presentaron cargos contra Nicholson, en realidad jugó en el juego en el que se alegaba que se le pagaría para no jugar .
Nicholson se asoció con Young por tercera vez en la liga nacional de fútbol de Australia, ambos jugando para Wollongong Wolves , ganando el campeonato de la liga nacional de fútbol en su primera temporada. [ cita requerida ] Fue utilizado principalmente como suplente, ya que era difícil desalojar al internacional australiano Scott Chipperfield , pero alcanzó un estatus de culto entre los aficionados de los Wolves. [ cita requerida ]