Family Health Strategy, the primary health care program in Brazil, has been scaled up throughout the country, but its expansion has been heterogeneous across municipalities. We investigate if there are unique municipal characteristics that can explain the timing of uptake and the pattern of expansion of the Family Health Strategy from years 1998 to 2012. We categorized municipalities in six groups based on the relative speed of the Family Health Strategy uptake and the pattern of Family Health Strategy coverage expansion. We assembled data for 11 indicators for years 2000 and 2010, for 5,507 municipalities, and assessed differences in indicators across the six groups, which we mapped to examine spatial heterogeneities. Important factors differentiating early and late adopters of the Family Health Strategy were supply of doctors and population density. Sustained coverage expansion was related mainly to population size, marginal benefits of the program and doctors’ supply. The uptake was widespread nationwide with no distinct patterns among regions, but highly heterogeneous at the state and municipal level. The Brazilian experience of expanding primary health care offers three lessons in relation to factors influencing diffusion of primary health care. First, the funding mechanism is critical for program implementation, and must be accompanied by ways to support the supply of primary care physicians in low density areas. Second, in more developed and bigger areas the main challenge is lack of incentives to pursue universal coverage, especially due to the availability of private insurance. Third, population size is a crucial element to guarantee coverage sustainability over time.