Stability properties of large-amplitude, relativistic non-linear plasma waves are investigated by solving the Cauchy problem for the motion of a relativistic electron fluid with uniform stationary ion background. The development of a stationary large-amplitude relativistic wave is studied under the influence of initial perturbations of electric field and particle velocities. Stochastic initial perturbations are slightly damped with time; in the case of parametric initial perturbations, a perturbation growth is followed by non-linear saturation and decay. Under some conditions, particle interstreaming can develop but it does not significantly influence the large potential wells in the wave.