Research showed that the capacity of making simple estimations begins to develop already at the age of five, but little is known about the early development of this estimation capacity and the strategies that underly it. The current study longitudinally followed the estimation capacity and strategies of 332 children from first to second grade of primary school by gathering strategy information through immediate trial-by-trial verbal reports on 14 addition items divided over six number size levels. Both in first and second grade children already used strategies that exhibited a basic understanding of computational estimation. For instance, their verbalizations suggested that they knew that a good estimate had to be close to the exact answer without necessarily coinciding with it. In addition to these rudimentary computational estimation strategies, we observed an increasing urge in those children to solve computational estimation problems by means of exact arithmetic. Implications for the earlier introduction of computational estimation in primary mathematics education are discussed.