Bacteriophages are the largest reservoir of genetic diversity. Here we describe the novel phage ΦJM-2012. This natural isolate from marine Vibrio cyclitrophicus possesses very few gene contents relevant to other well-studied marine Vibrio phages. To better understand its evolutionary history, we built a mathematical model of pairwise relationships among 1,221 phage genomes, in which the genomes (nodes) are linked by edges representing the normalized number of shared orthologous protein families. This weighted network revealed that ΦJM-2012 was connected to only five members of the Pseudomonas ΦKZ-like phage family in an isolated network, strongly indicating that it belongs to this phage group. However, comparative genomic analyses highlighted an almost complete loss of colinearity with the ΦKZ-related genomes and little conservation of gene order, probably reflecting the action of distinct evolutionary forces on the genome of ΦJM-2012. In this phage, typical conserved core genes, including six RNA polymerase genes, were frequently displaced and the hyperplastic regions were rich in both unique genes and predicted unidirectional promoters with highly correlated orientations. Further, analysis of the ΦJM-2012 genome showed that segments of the conserved N-terminal parts of ΦKZ tail fiber paralogs exhibited evidence of combinatorial assortment, having switched transcriptional orientation, and there was recruitment and/or structural changes among phage endolysins and tail spike protein. Thus, this naturally occurring phage appears to have branched from a common ancestor of the ΦKZ-related groups, showing a distinct genomic architecture and unique genes that most likely reflect adaptation to its chosen host and environment.