A number of childhood vaccination programmes have recently introduced vaccination against Streptococcus pneumoniae, the pneumococcus, a major cause of pneumonia and meningitis. The pneumococcal conjugate vaccines (PCVs) that are currently in use only protect against some serotypes of the bacterium, and there is now strong evidence that those serotypes not included in the vaccine increase in prevalence among most vaccinated populations. We present a mathematical model for the dynamics of nasopharyngeal carriage of S. pneumoniae that allows for carriage with multiple serotypes. The model is used to predict the prevalence of vaccine type (VT) and non-VT (NVT) serotypes following the introduction of PCV. Parameter estimates for the model are obtained by maximum likelihood using pre-vaccination data from The Gambia. The model predicts that low (1, 6A and 9V) and medium (4, 5, 7F, 14, 18C, 19A and 19F) prevalence serotypes can be eliminated through vaccination, but that the overall prevalence of carriage will be reduced only slightly because of an increase in the prevalence of NVT serotypes. Serotype replacement will be sequential, with high and medium prevalence NVT serotypes dominating initially, followed by an increase of serotypes of low prevalence. We examine the impact of a hypothetical vaccine that provides partial protection against all serotypes, and find that this reduces overall carriage, but is unable to eliminate low or medium prevalence serotypes.