An adaptation of the full configuration interaction quantum Monte Carlo (FCIQMC) method is presented, for correlated electron problems containing heavy elements and the presence of significant relativistic effects. The modified algorithm allows for the sampling of the four-component spinors of the Dirac--Coulomb(--Breit) Hamiltonian within the relativistic no-pair approximation. The loss of spin symmetry and the general requirement for complex-valued Hamiltonian matrix elements are the most immediate considerations in expanding the scope of FCIQMC into the relativistic domain, and the alternatives for their efficient implementation are motivated and demonstrated. For the canonical correlated four-component chemical benchmark application of Thallium Hydride, we show that the necessary modifications do not particularly adversely affect the convergence of the systematic (initiator) error to the exact correlation energy for FCIQMC calculations, which is primarily dictated by the sparsity of the wave function, allowing the computational effort to somewhat bypass the formal increases in Hilbert space dimension for these problems. We apply the method to the larger problem of the spectroscopic constants of Tin Oxide, correlating 28 electrons in 122 Kramers-paired spinors, finding good agreement with experimental and prior theoretical relativistic studies.