The classical bordetellae are comprised of three subspecies that differ from broad to very limited host specificity. Although several lineages appear to have specialized to particular host species, most retain the ability to colonize and grow in mice, providing a powerful common experimental model to study their differences. One of the subspecies, Bordetella parapertussis, is composed of two distinct clades that have specialized to different hosts: one to humans (Bpphu), and the other to sheep (Bppov). While Bpphu and the other classical bordetellae can efficiently colonize mice, Bppov strains are severely defective in their ability to colonize the murine respiratory tract. Bppov genomic analysis did not reveal the loss of adherence genes, but substantial mutations and deletions of multiple genes involved in the production of O-antigen, which is required to prevent complement deposition on B. bronchiseptica and Bpphu strains. Bppov lacks O-antigen and, like O-antigen mutants of other bordetellae, is highly sensitive to murine complement-mediated killing in vitro. Based on these results, we hypothesized that Bppov failed to colonize mice because of its sensitivity to murine complement. Consistent with this, the Bppov defect in the colonization of wild type mice was not observed in mice lacking the central complement component C3. Furthermore, Bppov strains were highly susceptible to killing by murine complement, but not by sheep complement. These data demonstrate that the failure of Bppov to colonize mice is due to sensitivity to murine, but not sheep, complement, providing a mechanistic example of how specialization that accompanies expansion in one host can limit host range.