We present a new relativistic formulation for the calculation of nuclear magnetic resonance (NMR) shielding tensors. The formulation makes use of gauge-including atomic orbitals and is based on density functional theory. The relativistic effects are included by making use of the zeroth-order regular approximation. This formulation has been implemented and the Hg-199 NMR shifts of HgMe2, HgMeCN, Hg(CN)(2), HgMeCl, HgMeBr, HgMeI, HgCl2, HgBr2, and HgI2 have been calculated using both experimental and optimized geometries. For experimental geometries, good qualitative agreement with experiment is obtained. Quantitatively, the calculated results deviate from experiment on average by 163 ppm, which is approximately 3% of the range of Hg-199 NMR. The experimental effects of an electron donating solvent on the mercury shifts have been reproduced with calculations on HgCl2(NH3)(2), HgBr2(NH3)(2), and HgI2(NH3)(2). In addition, it is shown that the mercury NMR shieldings are sensitive to geometry with changes for HgCl2 of approximately 50 ppm for each 0.01 Angstrom change in bond length, and 100 ppm for each 10 degrees change in bond angle.