Randell excelled as a rugby player, cricketer, and student at Lindisfarne College near Hastings and represented the First XV from the age of 14.
In 1999, Randell captaining the Otago Highlanders to an 8–3 regular season record and subsequently to the 1999 Super 12 Final where they lost to the Canterbury Crusaders in a closely fought match 24–19.
Randell's low moment came during the 1999 Rugby World Cup where he led the team during the defeat to France in the semi-final.
Randell left New Zealand to spend a month in Florida in the United States to get away from the negative media spotlight.
[citation needed] After this defeat, Todd Blackadder became captain, although Randell retained his place in the team for 2000–2002.
He missed all of the 2002 Tri-Nations series, but after his form in the 2002 Super 12 season earned him a recall to captain the All Blacks on the end of the year tour of England, France and Wales.