The structure of relativistic radiation mediated shocks (RRMS) propagating into a cold electron-proton plasma is calculated and analyzed. A qualitative discussion of the physics of relativistic and non relativistic shocks, including order of magnitude estimates for the relevant temperature and length scales, is presented. Detailed numerical solutions are derived for shock Lorentz factors $\Gamma_u$ in the range $6\le\Gamma_u\le30$, using a novel iteration technique solving the hydrodynamics and radiation transport equations (the protons, electrons and positrons are argued to be coupled by collective plasma processes and are treated as a fluid). The shock transition (deceleration) region, where the Lorentz factor $\Gamma$ drops from $\Gamma_u$ to $\sim 1$, is characterized by high plasma temperatures $T\sim \Gamma m_ec^2$ and highly anisotropic radiation, with characteristic shock-frame energy of upstream and downstream going photons of a few~$\times\, m_ec^2$ and $\sim \Gamma^2 m_ec^2$, respectively.Photon scattering is dominated by e$^\pm$ pairs, with pair to proton density ratio reaching $\approx10^2\Gamma_u$. The width of the deceleration region, in terms of Thomson optical depths for upstream going photons, is large, $\Delta\tau\sim\Gamma_u^2$ ($\Delta\tau\sim1$ neglecting the contribution of pairs) due to Klein Nishina suppression of the scattering cross section. A high energy photon component, narrowly beamed in the downstream direction, with a nearly flat power-law like spectrum, $\nu I_\nu\propto\nu^0$, and an energy cutoff at $\sim \Gamma_u^2 m_ec^2$ carries a fair fraction of the energy flux at the end of the deceleration region. An approximate analytic model of RRMS, reproducing the main features of the numerical results, is provided.