The synchronization of two stochastically coupled one-dimensional cellular automata (CA) is analyzed. It is shown that the transition to synchronization is characterized by a dramatic increase of the statistical complexity of the patterns generated by the difference automaton. This singular behavior is verified to be present in several CA rules displaying complex behavior.