In order to engineer the choline oxidase from Arthrobacter nicotianae (An_CodA) for the potential application as biological bleach in detergents, the specific activity of the enzyme toward the synthetic substrate tris-(2-hydroxyethyl)-methylammonium methylsulfate (MTEA) was improved by methods of directed evolution and rational design. The best mutants (up to 520% wt-activity with MTEA) revealed mutations in the FAD- (A21V, G62D, I69V) and substrate-binding site (S348L, V349L, F351Y). In a separate screening of a library comprising of randomly mutagenised An_CodA, with the natural substrate choline, four mutations were identified, which were further combined in one clone. The constructed clone showed improved activity towards both substrates, MTEA and choline. Mapping these mutation sites onto the structural model of An_CodA revealed that Phe351 is positioned right in the active site of An_CodA and very likely interacts with the bound substrate. Ala21 is part of an alpha-helix which interacts with the diphosphate moiety of the flavin cofactor and might influence the activity and specificity of the enzyme.