Background and Objective: The aim of this study is to analyze the relationship between the subgingival colonization by Candida albicans and other yeasts with the severity of chronic periodontitis (CP). Material and Methods: After sample size calculation, 40 patients with CP and 20 healthy subjects (HS) were included in the study. Cases of slight-moderate (MCP, n = 23) and severe CP (SCP, n = 17) were defined according to the Centers for Disease Control/American Association of Periodontology classification. Subgingival samples were acquired using sterile paper-points from the sulcus or the deepest periodontal pocket of each healthy and subject with CP, respectively, and were cultured aerobically on three selective media. Yeast colonies that grew on the surface of plates were later identified by biochemical reactions. Statistical tests were used to analyze the association between subgingival yeast colonization (number of yeast-positive individuals and colony forming units (CFU) per subject) and periodontal disease status, considering statistical significance when P < 0.05. Results: Although several yeast species were found (C. parapisilosis, Rhodotorula sp., C. dubliniensis and C. tropicalis), only C. albicans was present in all the patients with yeast-positive CP. Twelve patients (30%) with CP presented yeasts in the subgingival biofilm while only three patients (15%) in the HS group were positive for these microorganisms. No statistical difference was found between the CP and HS groups (P = 0.084). However, when the CP group was divided on the basis of severity, statistical differences were observed between the SCP and MCP groups (47% vs. 17%, P = 0.043), and between the SCP and HS groups (47% vs. 15%, P = 0.033). No statistical difference was observed between the MCP and HS groups (17% vs. 15%, P = 0.832). High densities of yeasts were found only in patients with MCP and SCP (mean and range 61.25 (0–100) CFU/plate and mean and range 51 (0–101) CFU/plate, respectively). Conclusion: In this group of patients, subgingival colonization of some yeasts, especially C. albicans, was associated with the severity of CP.