This study aimed to evaluate access to and utilization of various types of dental services by individuals 18 years or older in Brazil’s State capitals. We gathered data from the Telephone Survey Surveillance System for Risk and Protective Factors for Chronic Diseases (VIGITEL) in 2009 (n = 54,367). More than half of the target population reported the need for dental treatment in the previous year; of these, 15.2% lacked access to dental services when needed. The private sector provided 61.1% of all dental appointments. The share of services provided by the Unified National Health System (SUS) ranged from 6.2% in the Federal District to 35.2% in Boa Vista, in the North. Multivariate Poisson regression models showed higher prevalence of dental treatment needs among women, middle-aged adults, and individuals with more schooling. Lack of access to dental care was more frequent among women, young adults, less educated individuals, and among lightenerskinned blacks. Our findings highlight sharp inequalities in the use of and access to dental services in the Brazilian State capitals.