To investigate factors associated with dental caries in deciduous dentition, a nested case-control study was conducted in a prevalence survey of preschool children (n = 1,690) aged 18 to 36 months and 5 years of age, treated under the Family Health Program in Recife, Pernambuco State, Brazil, in 2006. Cases were children with dmft > 1 and controls with dmft = 0. The independent variables were analyzed in blocks: demographic, environmental, family structure, health care, and dental services use. OR and 95%CI were estimated. Variables associated with the outcome at p < 0.20 in the univariate analysis were included in a multivariate logistic regression model. The cutoff for remaining in the final model was p < 0.10. Larger households (more members), lack of running supply, time of residence, maternal (or caregiver's) schooling, attendance in public preschool, demand for dental services, and sugar intake patterns were associated factors. Variables related to social context were the main predictors of caries, thus highlighting the need for comprehensive measures to address other common childhood health problems.