The bacterial genus Staphylococcus comprises a large group of pathogenic and non-pathogenic species associated with an array of host-species. Staphylococci are differentiated into coagulase-positive or coagulase-negative groups based on the capacity to promote clotting of plasma, a phenotype historically associated with the ability to cause disease. However, the genetic basis of this important diagnostic and pathogenic trait across the genus has not been examined to date. Here, we selected 54 representative staphylococcal species and subspecies to examine coagulation of plasma derived from six representative host-species. In total, 13 staphylococcal species mediated coagulation of plasma from at least one host-species including one previously identified as coagulase-negative (Staphylococcus condimenti). Comparative genomic analysis revealed that coagulase activity correlated with presence of a gene (vwb) encoding the von Willebrand binding protein (vWbp) whereas only the Staphylococcus aureus complex contained a gene encoding Staphylocoagulase (Coa), the classical mediator of coagulation. Importantly, S. aureus retained vwb-dependent coagulase activity in a S. aureus strain deleted for coa whereas deletion of vwb in Staphylococcus pseudintermedius resulted in loss of coagulase activity. Whole genome based phylogenetic reconstruction of the Staphylococcus genus revealed that the vwb gene has been acquired on at least four different occasions during the evolution of the Staphylococcus genus followed by allelic diversification via mutation and recombination. Allelic variants of vWbp from selected coagulase-positive Staphylococci mediated coagulation in a host-dependent manner indicative of host-adaptive evolution. Taken together, we have determined the genetic and evolutionary basis of staphylococcal coagulation revealing vWbp to be its archetypal determinant.