Al in 1996 werd André NK kortebaan bij de Junioren. Hij reed dat jaar voor het eerst op klapschaatsen.
In 1998 werd hij in Heerenveen Nederlands kampioen op de kortebaan, voor Sander Velt en nummer drie Jacob Kleibeuker. Het jaar daarna werd hij opnieuw kampioen, nu voor Dennis Kalker en Jacob Kleibeuker.