We consider the Landau Hamiltonian H-0, self-adjoint in L-2 (R-2), whose spectrum consists of an arithmetic progression of infinitely degenerate positive eigenvalues Lambda(q), q is an element of Z(+). We perturb H-0 by a non-local potential written as a bounded pseudo-differential operator Op(w)(V) with real-valued Weyl symbol V, such that Op(w)(V)H-0(-1) is compact. We study the spectral properties of the perturbed operator H-V = H-0 Op(w)(V). First, we construct symbols V, possessing a suitable symmetry, such that the operator H-V admits an explicit eigenbasis in L-2 (R-2), and calculate the corresponding eigenvalues. Moreover, for V which are not supposed to have this symmetry, we study the asymptotic distribution of the eigenvalues of H-V adjoining any given Lambda(q). We find that the effective Hamiltonian in this context is the Toeplitz operator T-q(V) = p(q)Op(w)(V)p(q), where p(q) is the orthogonal projection onto Ker(H-0 - Lambda I-q), and investigate its spectral asymptotics.