Background: Measles vaccine (MV) may protect against non-measles mortality. We tested whether survival depended on age of measles vaccination. Methods: Bandim Health Project follows children under 5 years of age through a Health and Demographic Surveillance System in rural Guinea-Bissau. Children aged 6-36 months with a vaccination card inspected were followed to the next visit or for a maximum of 6 months. In Cox proportional-hazards models adjusted for age and village cluster, we compared the survival of children vaccinated with MV early (< 9 months), as recommended (9-11 months) or late (> 12+ months) with the survival of measles-unvaccinated children. Among measles-vaccinated children, we modelled the effect of age at measles vaccination linearly to assess mortality changes per month increase in vaccination age. Results: From 1999 to 2006, 14,813 children (31,725 observations) were included. Children vaccinated with MV had a Hazard Ratio (HR) of 0.76 (95% CI: 0.63-0.91) compared with measles-unvaccinated children; censoring measles deaths did not change the results (HR = 0.79 (0.65-0.95)). For early MV the HR was 0.68 (0.53-0.87), for MV as recommended the HR was 0.77 (0.62-0.96) and for late MV the HR was 0.86 (0.67-1.11). Limiting the analysis to measles-vaccinated children, age at measles vaccination was associated with a 2.6% (0.4-5.1%) increase in mortality per month increase in vaccination age. Conclusion: Early MV was associated with a large survival advantage. The current policy to increase vaccination age, when measles control improves, may not optimize the impact of MV on child survival.