In the current report, we describe the identification of three genetically distinct groups of prophages integrated into three different chromosomal sites of human gut-associated Bifidobacterium breve and Bifidobacterium longum strains. These bifidobacterial prophages are distantly related to temperate actinobacteriophages of several hosts. Some prophages, integrated within the dnaJ2 gene, are competent for induction, excision, replication, assembly and lysis, suggesting that they are fully functional and can generate infectious particles, even though permissive hosts have not yet been identified. Interestingly, several of these phages harbor a putative phase variation shufflon (the Rin system) that generates variation of the tail-associated receptor binding protein (RBP). Unlike the analogous coliphage-associated shufflon Min, or simpler Cin and Gin inversion systems, Rin is predicted to use a tyrosine recombinase to promote inversion, the first reported phage-encoded tyrosine-family DNA invertase. The identification of bifidobacterial prophages with RBP diversification systems that are competent for assembly and lysis, yet fail to propagate lytically under laboratory conditions, suggests dynamic evolution of bifidobacteria and their phages in the human gut.