Introduction: Dental caries is one of the major widespread health issues that continue to negatively affect the oral health of children globally. Aim: To estimate the prevalence of dental caries and its risk factors among preschool children of Bhubaneswar, Odisha, India. Materials and methods: The study was a community-based cross-sectional one among preschool children with (N = 425) participants recruited from the Anganwadi centers (AWCs) of Bhubaneswar, Odisha, India. By using a cross-sectional study design, dental caries was assessed using the World Health Organization (WHO) guidelines, and other socioeconomic and risk factors data were collected through parental interview using questionnaires. Caries was identified at both tooth and surface levels through visual dental examinations by trained and calibrated dentists. Logistic regression analyses were used to identify associations among variables and caries. Results: The proportion of preschool children suffering from dental caries was found to be 47.29%. The multivariableadjusted model depicted that longer duration of breastfeeding was a significant predictor as follows: Those who had breastfed for more than 36 months [adjusted odds ratio (AOR): 5.41; 95% confidence interval (CI): 2.97–9.85; p = 0.001], 12 to 24 months (AOR: 2.1; 95% CI: 1.04–4.36; p = 0.037), followed by increase in age 61 to 72 months (AOR: 5.39; 95% CI: 2.72–10.67; p = 0.001), 49 to 60 months (AOR: 2.53; 95% CI: 1.41–4.52; p = 0.002), more than two children in the family (AOR: 2.70; 95% CI: 1.55–4.69; p = 0.001), and children who did not brush the teeth under the parent's supervision (AOR: 2.70; 95% CI: 1.55–4.69; p = 0.001). Conclusion: The study highlights the need to increase awareness about the oral health and hygiene among parents of preschool children in India.