En 1996, Stijn Vanstraelen devient champion provincial du Limbourg chez les juniors (moins de 17 ans). Quatre ans plus tard, il s'impose sur une étape du Tour du Brabant flamand. Il réalise également une bonne saison 2001 en remportant le Challenge de Hesbaye, ou encore une étape au Tour du Limbourg amateurs et au Triptyque des Barrages[2].
Los de la saison 2002, il évolue durant quelques mois au sein de l'équipe professionnelle RDM-Flanders. Avec cette formation, il obtient son meilleur résultat sur le continent asiatique en terminant deuxième d'une étape du Tour du Japon[3]. Il finit par ailleurs septième du Samyn et huitième du Circuit de Campine.