In last years, the considerable attention is paid to development of the theory and methods of binary sequential machines (SM), i.e. SM over the finite field GF(2), because the binary SM are widely used in the modern telecommunication systems, computer engineering, technical diagnostics, technological processes control. An algorithm is suggested for constructing orthogonal test sequences for binary multidimensional nonlinear sequential cellular machines which could find the application int he systems of optimal synthesis of binary multidimensional nonlinear sequential cellular machines.