The present invention relates to recombinant C. difficile toxin A (TcdA) and toxin B (TcdB) and binary toxin A (CDTa) proteins comprising specifically defined mutations relative to the native toxin sequence that substantially reduce or eliminate toxicity. The invention also relates to vaccines and immunogenic compositions comprising these recombinant toxins, as well as combinations of these toxins with binary toxin B (CDTb), which are capable of providing protection against C. difficile infection and/or the effects thereof. The invention also relates to methods of inducing an immune response to C. difficile comprising administering the vaccines and immunogenic compositions described herein to a patient. The invention also encompasses methods of expressing recombinant C. difficile toxin A and toxin B and CDTa mutants and CDTb in recombinant expression systems. In exemplary embodiments, TcdA, TcdB, and CDTa mutant toxins comprising sufficient mutations to substantially reduce or eliminate toxicity are expressed in the baculovirus/insect cell expression system.