We present analytical and numerical studies of the dynamics of relativistic electron and ion holes in a collisionless plasma. Electromagnetic radiation can be trapped in relativistic electron phase-space holes mainly due to the relativistic mass increase of the electrons that are accelerated by the potential of the phase-space hole and by the quivering component of the electromagnetic field. Relativistic ion holes may exist in plasmas where the electrons are thermalized to extremely ultra-relativistic energies. They may be responsible for the acceleration of particles to GeV energies in active galactic nuclei and supernova remnant shocks. The analytic solutions are employed as initial conditions for numerical simulations in which the dynamics and stability of the phase-space holes are investigated. The results have relevance for intense laser–plasma experiments and for astrophysical plasmas.