Bacteriophage D3112 represents one of two distinct groups of transposable phage found in the clinically relevant, opportunistic pathogen Pseudomonas aeruginosa. To further our understanding of transposable phage in P. aeruginosa, we have sequenced the complete genome of D3112. The genome is 37,611 bp, with an overall G+C content of 65%. We have identified 53 potential open reading frames, including three genes (the c repressor gene and early genes A and B) that have been previously characterized and sequenced. The organization of the putative coding regions corresponds to published genetic and transcriptional maps and is very similar to that of enterobacteriophage Mu. In contrast, the International Committee on Taxonomy of Viruses has classified D3112 as a X-like phage on the basis of its morphology. Similarity-based analyses identified 27 open reading frames with significant matches to proteins in the NCBI databases. Forty-eight percent of these were similar to Mu-like phage and prophage sequences, including proteins responsible for transposition, transcriptional regulation, virion morphogenesis, and capsid formation. The tail proteins were highly similar to prophage sequences in Escherichia coli and phage Phi12 from Staphylococcus aureus, while proteins at the right end were highly similar to proteins in Xylella fastidiosa. We performed phylogenetic analyses to understand the evolutionary relationships of D3112 with respect to Mu-like versus X-like bacteriophages. Different results were obtained from similarity-based versus phylogenetic analyses in some instances. Overall, our findings reveal a highly mosaic structure and suggest that extensive horizontal exchange of genetic material played an important role in the evolution of D3112.