The oral microbiome plays a key role for caries, periodontitis and systemic diseases. A method for rapid, high resolution, robust taxonomic profiling of subgingival bacterial communities for early detection of periodontitis biomarkers would therefore be a useful tool for individualized medicine. Here we used Illumina sequencing of the V1-V2 and V5-V6 hypervariable regions of the 16S ribosomal RNA gene. A sample stratification pipeline was developed in a pilot study of 19 individuals, of which 9 had been diagnosed with chronic periodontitis. 523 operational taxonomic units (OTUs) were obtained from the V1-V2 region and 432 OTUs from the V5-V6 region. Key periodontal pathogens like Porphyromonas gingivalis, Treponema denticola and Tannerella forsythia could be identified at the species level with both primer sets. Principal Coordinate Analysis identified two outliers consistently independent of the hypervariable region and method of DNA extraction used. The linear discriminant analysis (LDA) effect size algorithm (LEfSe) identified 80 OTU-level biomarkers of periodontitis and 17 of health. Health and periodontitis related clusters of OTUs were identified using a connectivity analysis and confirmed previous studies with several thousands of samples. A machine learning algorithm was developed which was trained on all but one sample and then predicted the diagnosis of the left-out sample (jack-knife method). Using a combination of the ten best biomarkers, 15 out of 17 samples were correctly diagnosed. Training the algorithm on time-resolved community profiles might provide a highly sensitive tool to detect the onset of periodontitis.