Human microbiomes are predicted to assemble in a reproducible and ordered manner yet there is limited knowledge on the development of the complex bacterial communities that constitute the oral microbiome. The oral microbiome plays major roles in many oral diseases including early childhood caries (ECC), which afflicts up to 70% of children in some countries. Saliva contains oral bacteria that are indicative of the whole oral microbiome and may have the ability to reflect the dysbiosis in supragingival plaque communities that initiates the clinical manifestations of ECC. The aim of this study was to determine the assembly of the oral microbiome during the first four years of life and compare it with the clinical development of ECC. The oral microbiomes of 134 children enrolled in a birth cohort study were determined at six ages between two months and four years-of-age and their mother's oral microbiome was determined at a single time point. We identified and quantified 356 operational taxonomic units (OTUs) of bacteria in saliva by sequencing the V4 region of the bacterial 16S RNA genes. Bacterial alpha diversity increased from a mean of 31 OTUs in the saliva of infants at 1.9 months-of-age to 84 OTUs at 39 months-of-age. The oral microbiome showed a distinct shift in composition as the children matured. The microbiome data were compared with the clinical development of ECC in the cohort at 39, 48, and 60 months-of-age as determined by ICDAS-II assessment. Streptococcus mutans was the most discriminatory oral bacterial species between health and current disease, with an increased abundance in disease. Overall our study demonstrates an ordered temporal development of the oral microbiome, describes a limited core oral microbiome and indicates that saliva testing of infants may help predict ECC risk.