The Gam protein of transposable phage Mu is an ortholog of eukaryotic and bacterial Ku proteins, which carry out nonhomologous DNA end joining (NHEJ) with the help of dedicated ATP-dependent ligases. Many bacteria carry Gam homologs associated with either complete or defective Mu-like prophages, but the role of Gam in the life cycle of Mu or in bacteria is unknown. Here, we show that MuGam is part of a two-component bacterial NHEJ DNA repair system. Ensemble and single-molecule experiments reveal that MuGam binds to DNA ends, slows the progress of RecBCD exonuclease, promotes binding of NAD+-dependent Escherichia coli ligase A, and stimulates ligation. In vivo, Gam equally promotes both precise and imprecise joining of restriction enzyme-digested linear plasmid DNA, as well as of a double-strand break (DSB) at an engineered I-SceI site in the chromosome. Cell survival after the induced DSB is specific to the stationary phase. In long-term growth competition experiments, particularly upon treatment with a clastogen, the presence of gam in a Mu lysogen confers a distinct fitness advantage. We also show that the role of Gam in the life of phage Mu is related not to transposition but to protection of genomic Mu copies from RecBCD when viral DNA packaging begins. Taken together, our data show that MuGam provides bacteria with an NHEJ system and suggest that the resulting fitness advantage is a reason that bacteria continue to retain the gam gene in the absence of an intact prophage.