Poor accessibility of healthcare facilities is a major barrier for people with disabilities when seeking care. Yet, accessibility is rarely routinely audited. This study reports findings from the first national assessment of the accessibility of primary health care facilities, undertaken in Brazil. A national accessibility audit was conducted by trained staff of all 38,812 primary healthcare facilities in Brazil in 2012, using a 22-item structured questionnaire. An overall accessibility score was created (22 items), and three sub-scales: external accessibility (eight items), internal accessibility (eight items), information accessibility (six items). The main finding is that the overall accessibility score of primary care facilities in Brazil was low (mean of 22, standard deviation (SD) of 0.21, on a 0–100 scale). Accessibility of different aspects of the healthcare facilities was also low, including external space (mean = 31.0, SD = 2.0), internal space (18.9, 1.9) and accessibility features for people with other visual or hearing impairments (6.3, SD = 1.0). Scores were consistently better in the least poor regions of Brazil and in facilities in larger municipality size (indicating more urban areas). In conclusion, large-scale accessibility audits are feasible to undertake. Poor accessibility means that people with disabilities will experience difficulties in accessing healthcare, and this is a violation of their rights according to international and Brazilian laws.