The present invention provides attenuated P. multocida strains that elicit an immune response in animal P. multocida, compositions comprising said strains, methods of vaccination against P. multocida, and kits for use with such methods and compositions. The invention further provides novel, genetically-engineered mutations in P. multocida hyaD and nanPU genes, which are useful in the production of novel attenuated P. multocida bacterial strains.