Children and adults use various strategies to solve arithmetic problems such as 701–698. Many studies have investigated students’ strategy use at a specific time point, but our knowledge about the longitudinal changes in students’ strategy use in elementary school is limited. Using a multilevel latent transition analysis, we examined individual differences in strategy use in multi-digit addition and subtraction problems of 1,947 students measured at the end of Grade 3 and the end of Grade 4. The analysis identified five different strategy use profiles, with the three largest profiles (mostly written algorithms, mostly mental computations, and a combination of written algorithms and mental computations) characterizing the strategy use of the large majority of students. For strategy use change over time, the analysis identified heterogeneous learning paths from Grade 3 to Grade 4. Nearly half of the students remained in the same strategy profile, but the other half moved to another profile. Students’ prior arithmetic knowledge and gender affect both strategy use in Grade 3 and strategy change between Grade 3 and 4, with amplifying effects. The classroom characteristics classroom intellectual composition and mathematics textbook had an effect on students’ strategy use in Grade 3, but not on strategy change. In conclusion, the current study shows how students differ not only in their arithmetic strategy use at one specific point in time but also in their learning paths, and that both student and classroom factors have impact.