Véritable miraculé de la sélection suédoise, Wahlstedt a fait ses débuts en équipe nationale en janvier 1998 face au Etats-Unis, en tant qu'attaquant. Disparu de la circulation pendant 6 ans, et revenu au pays à Helsingborgs, après un passage chez les Danois de Esbjerg, Wahlstedt a fait une apparition surprise face au Portugal en match amical. Sa prestation fut tellement convaincante que Lars Lagerbäck a décidé de le prendre dans le groupe des 23 pour cet Euro portugais.