Objectives Few Indian studies have examined the relationship between birth size and stunting in children. Studies on recovery from stunting in India are even fewer. This study, thus, investigates the relationship between birth size and stunting in Andhra Pradesh, India. This study further examines the factors associated with recovery from stunting using a longitudinal data. Methods We used data from the three waves of Young Lives Study (YLS) conducted in Andhra Pradesh in the years 2002, 2006–2007, and 2009 respectively. We used data from 1965 children in wave 1 to examine the association between birth size and stunting. For examining the factors associated with recovery from stunting between 1 and 5 years of age, and between 5 and 8 years, we use data from 582 and 670 children who were stunted at age 1 and age 5 respectively. We use multivariable logistic regression models to fulfil the objectives of the paper. Results The children who were of average- or large- size at birth were significantly less likely to be stunted than children who were of small size at birth (OR 0.61 and 0.47 respectively). Children of average/tall mothers were 0.41 times less likely to be stunted than children of shorter mothers. Severely stunted children were less likely than other stunted children to recover from stunting between 1 and 5 years of age, and between 5 and 8 years. Mother’s height was statistically associated with recovery. Change in wealth status of the household was statistically associated with recovery between 1 and 5 years of age. In comparison, child immunization was associated with recovery between 5 and 8 years. Conclusions for Practice This study contributes to the understanding of the impact of birth size on childhood stunting, and to the extent of recovery from stunting in India. Further follow-up is necessary to demonstrate the impact during adolescence and adulthood.