The branched aerobic respiratory chain in Bacillus cereus comprises three terminal oxidases: cytochromes aa3, caa3, and bd. Cytochrome caa3 requires heme A for activity, which is produced from heme O by heme A synthase (CtaA). In this study, we deleted the ctaA gene in B. cereus AH187 strain, this deletion resulted in loss of cytochrome caa3 activity. Proteomics data indicated that B. cereus grown in glucose-containing medium compensates for the loss of cytochrome caa3 activity by remodeling its respiratory metabolism. This remodeling involves up-regulation of cytochrome aa3 and several proteins involved in redox stress response—to circumvent sub-optimal respiratory metabolism. CtaA deletion changed the surface-composition of B. cereus, affecting its motility, autoaggregation phenotype, and the kinetics of biofilm formation. Strikingly, proteome remodeling made the ctaA mutant more resistant to cold and exogenous oxidative stresses compared to its parent strain. Consequently, we hypothesized that ctaA inactivation could improve B. cereus fitness in a nutrient-limited environment.