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 some mild conditions that guarantee the 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.