Mycobacteriophages BPs, Angel and Halo are closely related viruses isolated from Mycobacterium smegmatis, and possess the smallest known mycobacteriophage genomes, 41,901 bp, 42,289 bp and 41,441 bp, respectively. Comparative genome analysis reveals a novel class of ultra-small mobile genetic elements; BPs and Halo each contain an insertion of the proposed mobile elements MPME1 and MPME2, respectively, at different locations, while Angel contains neither. The close similarity of the genomes provides a comparison of the pre- and post-integration sequences, revealing an unusual 6 bp insertion at one end of the element and no target duplication. Nine additional copies of these mobile elements are identified in a variety of different contexts in other mycobacteriophage genomes. In addition, BPs, Angel and Halo have an unusual lysogeny module in which the repressor and integrase genes are closely linked. The attP site is located within the repressor-coding region, such that prophage formation results in expression of a C-terminally truncated, but active, form of the repressor.