Perturbations in early life gut microbiota can have long-term impacts on host health. In this study, we investigated antimicrobial-induced temporal changes in diversity, stability, and compositions of gut microbiota in neonatal veal calves, with the objective of identifying microbial markers that predict diarrhea. A total of 220 samples from 63 calves in first 8 weeks of life were used in this study. The results suggest that increase in diversity and stability of gut microbiota over time was a feature of "healthy" (non-diarrheic) calves during early life. Therapeutic antimicrobials delayed the temporal development of diversity and taxa-function robustness (a measure of microbial stability). In addition, predicted genes associated with beta lactam and cationic antimicrobial peptide resistance were more abundant in gut microbiota of calves treated with therapeutic antimicrobials. Random forest machine learning algorithm revealed that Trueperella, Streptococcus, Dorea, uncultured Lachnospiraceae, Ruminococcus 2, and Erysipelatoclostridium may be key microbial markers that can differentiate "healthy" and "unhealthy" (diarrheic) gut microbiota, as they predicted early life diarrhea with an accuracy of 84.3%. Our findings suggest that diarrhea in veal calves may be predicted by the shift in early life gut microbiota, which may provide an opportunity for early intervention (e.g., prebiotics or probiotics) to improve calf health with reduced usage of antimicrobials.