We present here the results of the analysis of the complete genome sequence of a lytic bacteriophage, vB_ButM_GuL6, which is the first virus isolated from Buttiauxella. Electron microscopy revealed that vB_ButM_GuL6 belongs to the family Myoviridae, order Caudovirales. The genome of vB_ButM_GuL6 is a linear, circularly permuted 178,039-bp dsDNA molecule with a GC content of 43.4%. It has been predicted to contain 282 protein-coding genes and two tRNA genes, tRNA-Met and tRNA-Gly. Using bioinformatics approaches, 99 (36%) of the vB_ButM_GuL6 genes were assigned a putative function. Genome-wide comparisons and phylogenetic analysis indicated that vB_ButM_GuL6 represents a new species of the subfamily Tevenvirinae and is most closely related to Escherichia virus RB43. These phages, together with Cronobacter phages Miller, CfP1, and IME-CF2, likely form a new genus within the subfamily Tevenvirinae.