Anthrax edema factor (EF) is a calmodulin-dependent adenylate cyclase that converts adenosine triphosphate (ATP) into 3'-5'-cyclic adenosine monophosphate (cAMP), contributing to the establishment of Bacillus anthracis infections and the resulting pathophysiology. We show that EF adenylate cyclase toxin activity is strongly mediated by the N-end rule, and thus is dependent on the identity of the N-terminal amino acid. EF variants having different N-terminal residues varied by more than 100-fold in potency in cultured cells and mice. EF variants having unfavorable, destabilizing N-terminal residues showed much greater activity in cells when the E1 ubiquitin ligase was inactivated or when proteasome inhibitors were present. Taken together, these results show that EF is uniquely affected by ubiquitination and/or proteasomal degradation.