While attending Gosford High School, Fairleigh played for the Australian Schoolboys team in 1988. He made his first grade debut for the Bears in round 17 of 1989 and for ten seasons from 1990 was a permanent first grade player and North Sydney stalwart. In State of Origin game III of 1991, Fairleigh was selected for the New South Wales team on the interchange bench. He was not selected in 1992 but appeared again in 1993 off the interchange bench in games I & II and as a prop-forward in the run-on side of game III.
Although not selected for Origin in 1994, Fairleigh won the Rothman's Medal in 1994 with a record tally of 33 votes. Fairleigh earned a place in the Australian Test side against France when Bradley Clyde withdrew. At the end of the 1994 NSWRL season, he was one of the first forwards selected for the 1994 Kangaroo Tour. He appeared in twelve minor tour matches and two Tests scoring five tries on tour. He had been selected as a reserve for the second Test but withdrew on the morning of the match with a virus. He played in the third Test against Great Britain and in the sole test against France, scoring a try in the 74-0 drubbing. His Origin (and national) representative careers benefitted from the fracas of the Super League war and he appeared in all three games of the 1995 and 1997 series for a career total of ten appearances for the Blues. He was also selected in the Australian team to play against Fiji and Papua New Guinea in 1996. He was second in the Rothmans Medal in 1996 behind teammate Jason Taylor.