We identify conditions giving
large natural classes of partial differential operators for which it is possible to construct a complete set of Laplace invariants. In order to do that we investigate general properties of differential invariants of partial differential operators under gauge transformations and introduce a sufficient condition for a set of invariants to be complete. We also give a slightly stricter condition that guarantees existence of such a set. The proof is constructive. The method gives many examples of invariants previously known in the literature as well as many new examples including multidimensional.