Universal Health Coverage (UHC) is one of the United Nations Sustainable Development Goals (SDGs). Achieving UHC will require strong health systems to promote and deliver equitable and integrated healthcare services through primary healthcare (PHC). In Brazil, the Family Health Strategy (FHS) delivers PHC through the public health system. Created in 1994, the FHS covered almost 123 million individuals (63% of the Brazilian population) by 2015. The FHS has been associated with many health improvements, but gaps in coverage still remain. This article examines factors associated with the implementation and expansion of the FHS across 5419 Brazilian municipalities from 1998 to 2012. The proportion of the municipal population covered by the FHS over time was assessed using a longitudinal multilevel model for change that accounted for variables covering eight domains: economic development, healthcare supply, healthcare needs/access, availability of other sources of healthcare, political context, geographical isolation, regional characteristics and population size. Data were obtained from multiple publicly available sources. During the 15-year study period, national coverage of the FHS increased from 4.4% to 54%, with 58% of the municipalities having population coverage of 95% or more, and municipalities that had not adopted the programme decreased from 86.4% to 4.9%. The increase in FHS uptake and coverage was not homogenous across municipalities, and was positively associated with small population size, low population density, low coverage of private health insurance, low level of economic development, alignment of the political party of the Mayor and the state Governor, and availability of healthcare supply. Efforts to expand the FHS coverage will need to focus on increasing the availability of health personnel, devising financial incentives for municipalities to uptake/expand the FHS and devising new policies that encompass both private and public sectors.