Digital watermarking has gained importance in recent years in copyright protection and multimedia. This paper proposes a secure and novel watermarking system based on complemented Maximum Length Cellular Automata (MLCA) and Two-Dimension Cellular Automata Transform (2D CAT). In this watermarking scheme, the original watermark is first encrypted by complemented MLCA with the private keys, and then the encrypted watermark is embedded into the CAT domain of the cover image, at last use the inverse CAT for the transformed image, the watermarked image is obtained. Experiment results show that this new method is more secure and provides robust performance against watermarking attacks.