Preterm birth affects more than 10% of all births worldwide. Such infants are much more prone to Growth Faltering (GF), an issue that has been unsolved despite the implementation of numerous interventions aimed at optimizing preterm infant nutrition. To improve the ability for early prediction of GF risk for preterm infants we collected a comprehensive, large, and unique clinical and microbiome dataset from 3 different sites in the US and the UK. We use and extend machine learning methods for GF prediction from clinical data. We next extend graphical models to integrate time series clinical and microbiome data. A model that integrates clinical and microbiome data improves on the ability to predict GF when compared to models using clinical data only. Information on a small subset of the taxa is enough to help improve model accuracy and to predict interventions that can improve outcome. We show that a hierarchical classifier that only uses a subset of the taxa for a subset of the infants is both the most accurate and cost-effective method for GF prediction. Further analysis of the best classifiers enables the prediction of interventions that can improve outcome.