Clostridium difficile causes antibiotic-associated diarrhea and pseudomembraneous colitis and is responsible for a large and increasing fraction of hospital-acquired infections. Fecal microbiota transplantation (FMT) is an alternate treatment option for recurrent C. difficile infection (RCDI) refractory to antibiotic therapy. It has recently been discussed favorably in the clinical and scientific communities and is receiving increasing public attention. However, short- and long-term health consequences of FMT remain a concern, as the effects of the transplanted microbiota on the patient remain unknown. To shed light on microbial events associated with RCDI and treatment by FMT, we performed fecal microbiota analysis by 16S rRNA gene amplicon pyrosequencing of 14 pairs of healthy donors and RCDI patients treated successfully by FMT. Post-FMT patient and healthy donor samples collected up to one year after FMT were studied longitudinally, including one post-FMT patient with antibiotic-associated relapse three months after FMT. This analysis allowed us not only to confirm prior reports that RCDI is associated with reduced diversity and compositional changes in the fecal microbiota, but also to characterize previously undocumented post-FMT microbiota dynamics. Members of the Streptococcaceae, Enterococcaceae, or Enterobacteriaceae were significantly increased and putative butyrate producers, such as Lachnospiraceae and Ruminococcaceae were significantly reduced in samples from RCDI patients before FMT as compared to post-FMT patient and healthy donor samples. RCDI patient samples showed more case-specific variations than post-FMT patient and healthy donor samples. However, none of the bacterial groups were invariably associated with RCDI or successful treatment by FMT. Overall microbiota compositions in post-FMT patients, specifically abundances of the above-mentioned Firmicutes, continued to change for at least 16 weeks after FMT, suggesting that full microbiota recovery from RCDI may take much longer than expected based on the disappearance of diarrheal symptoms immediately after FMT.