BACKGROUND: In 2008, the GAVI Alliance funded the introduction of new vaccines (including pentavalent diphtheria-tetanus-pertussis [DTP] plus hepatitis B and Haemophilus influenzae type b antigens) in Guinea-Bissau. The introduction was accompanied by increased vaccination outreach services and a more restrictive wastage policy, including only vaccinating children younger than 12 months. We assessed coverage of all vaccines in the Expanded Program on Immunizations before and after the new vaccines' introduction, and the implications on child survival. METHODS: This observational cohort study used data from the Bandim Health Project, which has monitored vaccination status and mortality in randomly selected village clusters in Guinea-Bissau since 1990. We assessed the change in vaccination coverage using cohort data from children born in 2007 and 2009; analysed the proportion of children who received measles vaccine after 12 months of age using data from 1999-2006; and compared child mortality after age 12 months in children who had received measles vaccine and those who had not using data from 1999 to 2006. FINDINGS: The proportion of children who were fully vaccinated by 12 months of age was 53% (468 of 878) in the 2007 cohort and 53% (467 of 879) in the 2009 cohort (relative risk [RR] 1·00, 95% CI 0·89-1·11). Coverage of DTP-3 and pentavalent-3 increased from 73% (644 of 878) in 2007 to 81% (712 of 879) in 2009 (RR 1·10, 95% CI 1·04 -1·17); by contrast, the coverage of measles vaccination declined from 71% (620 of 878) to 66% (577 of 879; RR 0·93, 0·85-1·01). The effect of the changes was significantly different for DTP-3 coverage compared with measles vaccine coverage (p=0·002). After 12 months of age, the adjusted mortality rate ratio was 0·71 (95% CI 0·56-0·90) for children who had received measles vaccine compared with those who had not (0·59 [0·43-0·80] for girls and 0·87 [0·62-1·23] for boys). INTERPRETATION: The introduction of the new vaccination programme in 2008 was associated with increased coverage of DTP, but decreased coverage of measles vaccine. In 1999-2006, child mortality was higher in children who had not received measles vaccine than in those who had. FUNDING: DANIDA, European Research Council, the Danish Independent Research Council, European Union FP7 via OPTIMUNISE, and Danish National Research Foundation.