Pasteurella multocida is the causative agent of many diseases including fowl cholera, an often fatal disease of birds which causes considerable losses to poultry industries worldwide. P. multocida is a heterogeneous species with strains differentiated into 16 LPS types based on Heddleston serology. Both killed cell (bacterin) and live-attenuated vaccines are available but there is little understanding of the level of cross-protective immunity elicited by these vaccines as neither the accuracy of Heddleston serotyping nor the range of LPS structures produced by different P. multocida strains has been known. To test this, we first determined the LPS structures expressed by more than 60 P. multocida strains and assessed the accuracy of Heddleston serotyping. These analyses showed that there are many more than 16 LPS structures expressed by P. multocida field isolates with some strains producing multiple LPS types simultaneously. Importantly, Heddleston serotyping gave an accurate prediction of LPS structure only 35% of the time. We then assessed the cross-protective efficacy of both killed and live vaccines using a range of genetically and structurally defined P. multocida mutant strains expressing full length or truncated LPS structures. Killed-cell vaccines gave protection only against challenge strains expressing identical or nearly identical LPS. Conversely, the protective immunity conferred by live vaccines was largely independent of LPS structure. These data raise significant questions about the ability of existing P. multocida bacterins to protect against the wide range of P. multocida strains present in the field and suggest that live vaccines will have significantly improved efficacy.