Immunocompromised individuals are at high risk of developing Clostridium difficile-associated disease (CDAD). Fecal microbiota transplantation (FMT) is a highly effective therapy for refractory or recurrent CDAD and, despite safety concerns, has recently been offered to immunocompromised patients. We investigated the genomics of bacterial composition following FMT in immunocompromised patients over a 1-year period. Metagenomic, strain and gene-level bacterial dynamics were characterized in two CDAD-affected hematopoietic stem cell (HCT) recipients following FMT. We found alterations in gene content, including loss of virulence and antibiotic resistance genes. These alterations were accompanied by long-term bacterial divergence at the species and strain levels. Our findings suggest limited durability of the specific bacterial consortium introduced with FMT and indicate that alterations of the functional potential of the microbiome are more complex than can be inferred by taxonomic information alone. Our observation that FMT alone cannot induce long-term donor-like alterations of the microbiota of HCT recipients suggests that FMT cannot indefinitely supersede environmental and/or host factors in shaping bacterial composition.