Regulated expression of the genes for anthrax toxin proteins is essential for the virulence of the pathogenic bacterium Bacillus anthracis. Induction of toxin gene expression depends on several factors, including temperature, bicarbonate levels, and metabolic state of the cell. To identify factors that regulate toxin expression, transposon mutagenesis was performed under non-inducing conditions and mutants were isolated that untimely expressed high levels of toxin. A number of these mutations clustered in the haem biosynthetic and cytochrome c maturation pathways. Genetic analysis revealed that two haem-dependent, small c-type cytochromes, CccA and CccB, located on the extracellular surface of the cytoplasmic membrane, regulate toxin gene expression by affecting the expression of the master virulence regulator AtxA. Deregulated AtxA expression in early exponential phase resulted in increased expression of toxin genes in response to loss of the CccA-CccB signalling pathway. This is the first function identified for these two small c-type cytochromes of Bacillus species. Extension of the transposon screen identified a previously uncharacterized protein, BAS3568, highly conserved across many bacterial and archeal species, as involved in cytochrome c activity and virulence regulation. These findings are significant not only to virulence regulation in B. anthracis, but also to analysis of virulence regulation in many pathogenic bacteria and to the study of cytochrome c activity in Gram-positive bacteria.