We analyzed the spatial relation between incomplete vaccine coverage for children and the distance from vaccination services. This was a cross-sectional study of children from 13 to 35 months of age from the cities of São Luís (Maranhão State) and Ribeirão Preto (São Paulo State), Brazil, and from basic health units (UBS, in Portuguese). The sample consisted of 2,744 children from São Luís and 3,325 from Ribeirão Preto. Data about incomplete vaccine coverage for children were obtained from the BRISA birth cohorts. Data about the quality of UBS vaccination services were obtained from the first cycle of the Brazilian National Program for Improvement of Access and Quality of Basic Care (PMAQ-AB, in Portuguese). For the spatial analysis, we determined the distance between the residence of the children (with and without a complete vaccine calendar) and the vaccination services of the UBS (classified according to number of structural items). Incomplete vaccine coverage was more pronounced in São Luís, with greater percentages for human rotavirus and triple viral vaccines, with the latter being the least available. In Ribeirão Preto, incomplete BCG vaccine coverage was more pronounced, with the tetravalent vaccine being the least available. Children from the two cities showed similarities: most of them had adult mothers with 9 to 11 years of schooling and did not reside with siblings in the household. They also showed differences: in São Luís, most mothers belonged to the economic class C, while in Ribeirão Preto they belong to the A and B classes. In the two cities with different socioeconomic conditions, complete vaccine coverage seemed not to depend on the location or quality of the vaccination service. Although São Luís showed a better structure of the services, incomplete vaccine coverage was higher compared to Ribeirão Preto.