New steady‐state solutions are derived which describe electromagnetic waves strong enough to make plasma ions and electrons relativistic. A two‐fluid model is used throughout. The following solutions are studied: (1) Linearly polarized waves with phase velocity much greater thanc; (2) arbitrarily polarized waves with phase velocity nearc, in a cold uniform plasma; (3) circularly polarized waves in a uniform plasma characterized by a scalar pressure tensor. All of these waves are capable of propagating in normally overdense plasmas, due to nonlinearities introduced by relativistic effects. The propagation of relativistically strong waves in a density gradient is examined, for the example of a circularly polarized wave strong enough to make electrons but not ions relativistic. It is shown that such a wave propagates at constant energy flux despite the nonlinearity of the system. However, nonlinear effects can greatly increase the maximum plasma density at which a relativistically strong wave can propagate. Applications to laser‐plasma interactions and to pulsar environments are discussed.