High-order spatial discretizations of hyperbolic PDEs are often designed to have strong stability properties, such as monotonicity. We study explicit multistep Runge-Kutta strong stability preserving (SSP) time integration methods for use with such discretizations. We prove an upper bound on the SSP coefficient of explicit multistep Runge-Kutta methods of order two and above. Numerical optimization is used to find optimized explicit methods of up to five steps, eight stages, and tenth order. These methods are tested on the linear advection and nonlinear Buckley-Leverett equations, and the results for the observed total variation diminishing and/or positivity preserving time-step are presented.