Computational estimation is seen as an important mathematical competence. Little is known, however, about the mathematical skills that are predictive of early computational estimation development. The current study longitudinally followed a group of about 350 children at four time points: second (K2, 4-year-olds) and third grades of kindergarten (K3, 5-year-olds) and first (P1, 6-year-olds) and second (P2, 7-year-olds) grades of primary school. The computational estimation task was administered in two variants: a nonverbal variant, in which the problems were presented with manipulatives and children also answered using manipulatives was administered in K3 and P1; and a verbal variant, in which the problems were presented with Arabic numerals and children had to answer verbally was administered in P1 and P2. Furthermore, children's basic numerical skills and exact and approximate arithmetic skills were assessed in K2 and K3, respectively. Path analysis showed a positive autoregressive relationship between the verbal variants of the computational estimation task but not between the nonverbal ones. Basic numerical skills were important predictors for computational estimation at all time points. Approximate arithmetic positively contributed to nonverbal estimation, while exact arithmetic positively predicted verbal estimation. In sum, solid basic numerical and arithmetic skills support children when performing computational estimation. Future intervention research should further unravel the causal contribution of each of these basic numerical and arithmetic skills.