Overweight and underweight are common issues among children in Malaysia and thus, Malaysian government has launched several campaigns to combat these problems. Previous research show that BMI at certain age could be predicted earlier so that early intervention can be initiate. Most of the study are very specific to some locality and certain ethnic, make it hard to generalize to the whole Malaysian. This research aims to investigate significant positive predictors of changes in Body Mass Index (BMI) of young children aged from 12 months to 48 months and to develop a prediction model for their BMI status (normal, overweight, obese, risk of overweight, underweight, and severe underweight). Data consisting of 558 records with 16 attributes involving 18,226 children, who had registered at the National Child Data Centre (NCDC) were analyzed and predicted using the decision tree algorithms of Rapid miner. The BMI of 48 months-old children can be reliably predicted by their BMI statuses at the ages of 21, 24, 27, 36, 42, and 45 months, parents’ incomes, and gender while the BMI at the age of 20 months and below are the negative predictors. The prediction model developed in this study may help practitioners to monitor such children’s BMI, especially in detecting the signs of severe overweight, obesity, and underweight among such children. Such a BMI prediction model can be used to identify young children who are at risk of being overweight, obese, and underweight such that remedial interventions can be implemented promptly.