The purpose of this study was to evaluate the changes of health gaps between Indigenous and non-Indigenous children over time and to explore critical factors that contribute to the changes. We employed data consisting of two cohorts of Australian children: infant (0/1 year) and children (4/5 years) that are part of the Longitudinal Study of Australian Children. Health outcomes were measured by physical outcome index (POI) and parent-rated health during 2004, 2006 and 2008. We used first-order autoregressive modelling to examine the longitudinal relationship between the changes in health outcomes and possible contributing risk factors. The results showed that the trends of POIs between Indigenous and non-Indigenous children were closing, while the gap of parent-rated health between the two populations persisted. We found that health outcomes (both POI and parent-rated health) at an earlier time point (t - 1) were significant predictors of the outcomes at the later time point (t). Carer's depression status, socio-economic position and neighbourhood liveability had significant and consistent impacts on parent-rated health, but had only varying impacts on POIs between Indigenous and non-Indigenous children as well as between the birth cohorts at different time periods. Similarly, low birth weight, carer's binge drinking behaviour and other risk factors showed such varying impacts at a particular time period. The study implied that appropriate interventions accompanied by monitoring of health outcomes are necessary in order to decrease the health gaps between Indigenous and non-Indigenous children.