Willis made his provincial debut for Otago in 1999 and his Super Rugby debut for the Highlanders the following year, but found playing time difficult to come by on the same sides as incumbent All Black hooker Anton Oliver and fellow rising star Andrew Hore.
However, with Oliver back healthy Willis again found himself on the reserve bench for the 2003 Super Rugby and NPC seasons.
Despite a lack of playing time, he still managed to show his substantial ability in limited minutes - in the 2003 NPC he scored 5 tries despite making only 2 starts in 9 total appearances.
On 23 April 2008, Willis confirmed he was joining Welsh Celtic League side Newport Gwent Dragons for the following European season.
[3] Willis was first selected to the All Blacks for their end of year tour in 2001, where he made starts - and was named team captain - against Ireland A and Scotland A.