A density fitting approach for the Coulomb matrix representation within the four-component formulation of relativistic density-functional theory is presented. Our implementation, which uses G-spinor basis sets, shares all the advantages of those found in nonrelativistic quantum chemistry. We show that very accurate Coulomb energies may be obtained using a modest number of scalar auxiliary basis functions for molecules containing heavy atoms. The efficiency of this new implementation is demonstrated in a detailed study of the spectroscopic properties of the gold dimer, and its scaling behavior has been tested by calculations of some closed-shell gold clusters (Au2, Au3+, Au4, Au5+). The algorithm is found to scale as O(N3), just as it does in the nonrelativistic case, and represents a dramatic improvement in efficiency over the conventional approach in the calculation of the Coulomb matrix, with computation times that are reduced to less than 3% for Au2 and up to 1% in the case of Au5+.