The implementation of gauge theories on a four-dimensional anisotropic lattice with two distinct lattice spacings is discussed, with special attention to the case where two axes are finely and two axes are coarsely discretized. Feynman rules for the Wilson gauge action are derived and the renormalizability of the theory and the recovery of the continuum limit are analyzed. The calculation of the gluon propagator and the restoration of Lorentz invariance in on-shell states is presented to one-loop order in lattice perturbation theory for $SU(N_c)$ on both 2+2 and 3+1 lattices.