This article identifies novel factors involved in cholesterol reduction by probiotic bacteria, which were identified using genetic and proteomic approaches. Approximately 600 Lactobacillus acidophilus A4 mutants were created by random mutagenesis. The cholesterol-reducing ability of each mutant was determined and verified using two different methods: the o-phthalaldehyde assay and gas chromatographic analysis (GC). Among screened mutants, strain BA9 showed a dramatically diminished ability to reduce cholesterol, as demonstrated by a 7.7% reduction rate, while the parent strain had a more than 50% reduction rate. The transposon insertion site was mapped using inverse PCR (I-PCR), and it was determined using bioinformatic methods that the deleted region contained the Streptococcus thermophilus catabolite control protein A gene (ccpA). In addition, we have shown using two-dimensional gel electrophoresis (2-DE) that several proteins, including a transcription regulator, FMN-binding protein, major facilitator superfamily permease, glycogen phosphorylase, the YknV protein, and fructose/tagatose bisphosphate aldolase, were strongly regulated by the ccpA gene. In addition, in vivo experiments investigating ccpA function were conducted with rats. Rats fed wild-type L. acidophilus A4 showed a greater than 20% reduction in total serum cholesterol, but rats fed BA9 mutant L. acidophilus showed only an approximately 10% reduction in cholesterol. These results provide important insights into the mechanism by which these lactic acid bacteria reduce cholesterol.