Background: Brazil is the most populous country with a public, universal and free health care system. The National Program for Access and Quality Improvement in Primary Care (PMAQ) was created to improve the quality of primary health care (PHC). Objective: To evaluated whether progress generally has been made within Brazil’s PHC since PMAQ implementation, and if changes occurred uniformly in the country, while also identifying municipal characteristics that may have influenced the improvement. Methods: This is an observational study using data from PMAQ external evaluation (2012 and 2014), a 1200-item survey used to evaluate Brazilian PHC quality. After confirming the groupings of items using factor analysis, we created 23 composed indexes (CIs) related to infrastructure and work process. Results: On average, the large majority of CIs showed improvements between 2012 and 2014. Region and city size moderated changes in the PHC indices differently. Overall, there were better improvements in infrastructure in the Northeast compared with other country regions, and in smaller cities (10 000–20 000 people). Infrastructure indices appear to have improved equitably across the country. Work process improvements varied with city size and region. Conclusion: Despite similar support of PMAQ across the country, improvements are not predictable nor homogeneous. Non-uniform improvements were seen in Brazil’s PHC. Though we do not directly evaluate the effectiveness of the PMAQ (financial reward) method, these initial findings suggest that it is a potentially useful tool to improve health systems, but additional support may be needed in regions that lag behind in quality improvements.