Although algebra is a prerequisite for higher mathematics, few studies have examined the mathematical and cognitive capabilities that contribute to the development of algebra word problems solving skills. We examined changes in these relations from second to ninth grades. Using a cross-sequential design that spanned 4 years, children from 3 cohorts (M[subscript age] = 7.85, 10.05, and 12.32) were administered annual tests of algebra word problems, mathematical skills (mathematical relational tasks, arithmetic word problems), and cognitive capabilities (working memory, updating, inhibitory, task switching, and performance intelligence). The cross-sectional findings showed that ability to solve mathematical relational problems was associated strongly with performance in algebra word problems. Working memory and updating explained variance in the relational, but not the algebra problems. Using an autoregressive cross-lagged model with structured residuals to analyze the longitudinal data, we found relational and arithmetic performance predicted independently algebra performance from one year to the next. The strength of these relations was consistent across grades. These findings point to the importance of developing skills in relational problems as one of the tools for improving algebra performance.