We have generalized the exact solution of the Riemann problem in special relativistic hydrodynamics (Martí & Müller 1994) for arbitrary tangential flow velocities. The solution is obtained by solving the jump conditions across shocks plus an ordinary differential equation arising from the self-similarity condition along rarefaction waves, in a similar way as in purely normal flow. The dependence of the solution on the tangential velocities is analysed, and the impact of this result on the development of multi-dimensional relativistic hydrodynamic codes (of Godunov type) is discussed.