Streptococcus pneumoniae is a leading cause of pneumonia, the most common cause of childhood death. Papua New Guinean children experience high rates of nasopharyngeal pneumococcal colonization within weeks of birth, predisposing them to pneumococcal disease. In a trial to determine the safety and immunogenicity of early infant vaccination with 7-valent pneumococcal conjugate vaccine (7vPCV), we investigated the impact of early schedules on pneumococcal carriage. Infants were randomized at birth to receive 7vPCV in a 0–1–2-month (n = 101) or a 1–2–3-month (n = 105) schedule or no 7vPCV (n = 106). All children received 23-valent pneumococcal polysaccharide vaccine at age 9 months. We cultured nasopharyngeal swabs (NPS) collected at ages 1, 2, 3, 4 weeks and 3, 9, 18 months, and middle ear discharge if present. Pneumococcal serotypes were identified by the Quellung reaction. A total of 1761 NPS were cultured. The prevalence of pneumococcal carriage was 22% at 1 week of age, rising to 80% by age 3 months and remained >70% thereafter, with high-density carriage in 42% of pneumococcus-positive samples. We identified 63 different serotypes; 43% of isolates from controls were 13vPCV serotypes. There were no significant differences in 7vPCV serotype carriage between 7vPCV recipients and controls at any age (22% vs. 31% at 9 months, p = 0.2). At age 9 months the prevalence of non-7vPCV carriage was 17% higher in 7vPCV recipients (48%) than in controls (25%, p = 0.02). More non-7vPCV serotypes were isolated from ear discharge in 16 7vPCV recipients than from 4 controls (48% vs. 25%, p = 0.13). The limited impact of neonatal or accelerated infant 7vPCV schedules on vaccine serotype carriage is probably due to the early onset of dense carriage of a broad range of pneumococcal serotypes. While serotype-independent pneumococcal vaccines are needed in high-risk populations, the underlying environmental factors and sources of infection must be investigated. http://clinicaltrials.gov/ct2/show/NCT00219401.