The present invention provides attenuated M. haemolytica strains that elicit an immune response in animals against M. haemolytica, compositions comprising said strains, methods of vaccination against M. haemolytica, and kits for use with such methods and compositions. The invention further provides multi-valent vaccines, which provide protective immunity when administered in an effective amount to animals susceptible to “shipping fever” or bovine respiratory disease.