To investigate the formation and the propagation of relativistic shock waves in viscous gluon matter we solve the relativistic Riemann problem using a microscopic parton cascade. We demonstrate the transition from ideal to viscous shock waves by varying the shear viscosity to entropy density ratio $eta/s$. We show that an $eta/s$ ratio larger than 0.2 prevents the development of well-defined shock waves on time scales typical for ultrarelativistic heavy-ion collisions. These findings are confirmed by viscous hydrodynamic calculations.