We present a new Lattice Boltzmann (LB) formulation to solve the Maxwell equations for electromagnetic (EM) waves propagating in a heterogeneous medium. By using a pseudo-vector discrete Boltzmann distribution, the scheme is shown to reproduce the continuum Maxwell equations. The technique compares well with a pseudo-spectral method at solving for two-dimensional wave propagation in a heterogeneous medium, which by design contains substantial contrasts in the refractive index. The extension to three dimensions follows naturally and, owing to the recognized efficiency of LB schemes for parallel computation in irregular geometries, it gives a powerful method to numerically simulate a wide range of problems involving EM wave propagation in complex media.