The realization of artificial gauge fields and spin-orbit coupling for ultra-cold quantum gases promises new insight into paradigm solid state systems. Here we experimentally probe the dispersion relation of a spin-orbit coupled Bose-Einstein condensate loaded into a translating optical lattice by observing its dynamical stability, and develop an effective band structure that provides a theoretical understanding of the locations of the band edges. This system presents exciting new opportunities for engineering condensed-matter analogs using the flexible toolbox of ultra-cold quantum gases.