A formalism for phenomenologically including the effects of nearest-neighbor lattice relaxation on deep levels associated with substitutional impurities in semiconductors is outlined and used to investigate such effects in GaP and Si. This approach is an extension of the theory of Hjalmarson et al. [Phys. Rev. Lett. 44, 810 (1980)]. Lattice relaxation is accounted for by characterizing the nearest-neighbor off-diagonal matrix elements of the defect potential by parameters that depend on the impurity- and host-atom bond lengths. For symmetric, breathing-moderelaxations, only two parameters are needed, one each for the A1-symmetric and the T2-symmetric deep levels. By computing the A1- or T2-symmetric levels as a function of the appropriate parameter, the effects of varying amounts of lattice relaxation can be systematically explored. To determine these parameters for a specific impurity-host system, a variation of the inverse bond-length-squared scaling law is used. The results of applying this formalism to several impurities in GaP and Si are presented and compared with experimental data and with other theories.