Bacteria that replicate within eukaryotic host cells include a variety of pathogenic and mutualistic species. Early genome data for these intracellular associates suggested they experience continual gene loss, little if any gene acquisition, and minimal recombination in small, isolated populations. This view of reductive evolution is itself evolving as new genome sequences clarify mechanisms and outcomes of diverse intracellular associations. Recently sequenced genomes have confirmed a trajectory of gene loss and exceptional genome stability in long-term, nutritional mutualists and certain pathogens. However, new genome data for the Rickettsiales and Chlamydiales indicate more repeated DNA, a greater abundance of mobile DNA elements, and more labile genome dynamics than previously suspected for ancient intracellular lineages. Surprising discoveries of conjugation machinery in the parasite Rickettsia felis and the amoebae symbiont Parachlamydia sp. suggest that DNA transfer might play key roles in some intracellular taxa.