Negativicutes are gram-negative bacteria characterized by two cell membranes, but they are phylogenetically a side-branch of gram-positive Firmicutes that contain only a single membrane. We asked whether viruses (phages) infecting Negativicutes were horizontally acquired from gram-negative Proteobacteria, given the shared outer cell structure of their bacterial hosts, or if Negativicute phages co-evolved vertically with their hosts and thus resemble gram-positive Firmicute prophages. We predicted and characterized 485 prophages (mostly Caudovirales) from gram-negative Firmicute genomes plus 2977 prophages from other bacterial clades, and we used virome sequence data from 183 human stool samples to support our predictions. The majority of identified Negativicute prophages were lambdoids closer related to prophages from other Firmicutes than Proteobacteria by sequence relationship and genome organization (position of the lysis module). Only a single Mu-like candidate prophage and no clear P2-like prophages were identified in Negativicutes, both common in Proteobacteria. Given this collective evidence, it is unlikely that Negativicute phages were acquired from Proteobacteria. Sequence-related prophages, which occasionally harboured antibiotic resistance genes, were identified in two distinct Negativicute orders (Veillonellales and Acidaminococcales), possibly suggesting horizontal cross-order phage infection between human gut commensals. Our results reveal ancient genomic signatures of phage and bacteria co-evolution despite horizontal phage mobilization.