Live measles vaccine (MV) may have beneficial off-target/non-specific effects (NSEs) reducing child mortality beyond prevention of measles infection. In contrast, the non-live pentavalent (Diphtheria-Tetanus-Pertussis-H. influenzae Type B-Hepatitis B) vaccine has no beneficial NSEs. The NSEs are strongest for the most recent vaccine. Hence, sequence of vaccination may affect survival. In Guinea-Bissau, we followed 7094 measles-vaccinated children prospectively from first home visit after 9 months (when MV is scheduled) to 5 years of age. We compared survival by sequence of MV and third Pentavalent vaccine (Penta3; scheduled at 3½ months) in Cox proportional-hazards models. Compared with being vaccinated in-sequence (Penta3-then-MV), having received out-of-sequence Penta3-after-MV before the visit was associated with an adjusted Hazard Ratio (aHR) of 1.19 (95%CI: 0.84–1.69); Receiving missing Penta doses on the visit date tended to be associated with higher mortality (aHR = 1.87 (0.96–3.65)) while not receiving missing doses of Penta was not (aHR = 0.93 (0.57–1.54)), test for interaction p = 0.09.