Background: There is limited evidence on recent trends in childhood growth trajectories in Low-/middle-income countries. We investigated how age-trajectories for height and Body Mass Index (BMI) have changed among Brazilian children born in two different time periods after 2000. Methods: We used a population-based cohort (part of the “Cohort of 100-Million Brazilians”) created by the linkage of three Brazilian administrative databases: the Cadastro Único of the Federal Government, the National System of Live Births and the National Nutritional and Food Surveillance System. We included longitudinal data on 5,750,214 children who were 3 to <10 years of age and born between 2001 and 2014 (20,209,133 observations). We applied fractional polynomial models with random-effects to estimate mean height and BMI trajectories for children. Findings: Compared to children born in 2001–2007, the cohort born in 2008–2014 were on average taller, by a z-score of 0.15 in boys and 0.12 in girls. Their height trajectories shifted upwards, by approximately 1 cm in both sexes. Levels of BMI increased little, by a z-score of 0.06 (boys) and 0.04 (girls). Mean BMI trajectories also changed little. However, the prevalence of overweight/obesity increased between cohorts, e.g., from 26.8% to 30% in boys and 23.9%–26.6% in girls aged between 5 and <10 years. Interpretation: An increase of 1 cm in mean height of Brazilian children during a short period indicates the improvement in maternal and child health, especially those from low-income families due to the new health and welfare policies in Brazil. Although mean BMI changed little, the prevalence of child overweight/obesity slightly increased and remained high.