Obesity is an increasing public health concern worldwide. According to the latest Organization for Economic Co-operation and Development (OECD) report (2014), the incidence of child obesity in Korea has exceeded the OECD average. To better understand and control this condition, the present study examined the composition of the gut microbial community in normal and obese adolescents. Fecal samples were collected from 67 obese (body mass index [BMI] ≥ 30 kg/m2, or ≥ 99th BMI percentile) and 67 normal (BMI < 25 kg/m2 or < 85th BMI percentile) Korean adolescents aged 13-16 years and subjected to 16S rRNA gene sequencing. Analysis of bacterial composition according to taxonomic rank (genus, family, and phylum) revealed marked differences in the Bacteroides and Prevotella populations in normal and obese samples (p < 0.005) at the genus and family levels; however, there was no difference in the Firmicutes-to-Bacteroidetes (F/B) ratio between normal and obese adolescents samples at the phylum level (F/B normal = 0.50 ± 0.53; F/B obese = 0.56 ± 0.86; p = 0.384). Statistical analysis revealed a significant association between the compositions of several bacterial taxa and child obesity. Among these, Bacteroides and Prevotella showed the most significant association with BMI (p < 0.0001 and 0.0001, respectively). We also found that the composition of Bacteroides was negatively associated with triglycerides (TG), total cholesterol, and high-sensitive C-reactive protein (hs-crp) (p = 0.0049, 0.0023, and 0.0038, respectively) levels, whereas that of Prevotella was positively associated with TG and hs-crp levels (p = 0.0394 and 0.0150, respectively). We then applied the association rule mining algorithm to generate "rules" to identify the association between the populations of multiple bacterial taxa and obesity; these rules were able to discriminate obese from normal states. Therefore, the present study describes a systemic approach to identify the association between bacterial populations in the gut and childhood obesity.