Disease is an increasing threat to reef-building corals. One of the few identified pathogens of coral disease is the bacterium Vibrio coralliilyticus. In Vibrio cholerae, infection by a bacterial virus (bacteriophage) results in the conversion of non-pathogenic strains to pathogenic strains and this can lead to cholera pandemics. Pathogenicity islands encoded in the V. cholerae genome play an important role in pathogenesis. Here we analyse five whole genome sequences of V. coralliilyticus to examine whether virulence is similarly driven by horizontally acquired elements. We demonstrate that bacteriophage genomes encoding toxin genes with homology to those found in pathogenic V. cholerae are integrated in V. coralliilyticus genomes. Virulence factors located on chromosomal pathogenicity islands also exist in some strains of V. coralliilyticus. The presence of these genetic signatures indicates virulence in V. coralliilyticus is driven by prophages and other horizontally acquired elements. Screening for pathogens of coral disease should target conserved regions in these elements.