We consider the problems of counting and enumerating all orthogonal labelings in de Bruijn graphs, and show their link with the construction of orthogonal Latin squares based on Cellular Automata (CA).