Electric field gradients at the nuclei of halogen atoms are calculated using a finite field approach. The four-component Dirac-Coulomb Hamiltonian serves as the framework, all electrons are correlated by the relativistic Fock-space coupled cluster method with single and double excitations, and the Gaunt term, the main part of the Breit interaction, is included. Large basis sets (e.g., 28s24p21d9f4g2h Gaussian-type functions for I) are used. Combined with experimental nuclear quadrupole coupling constants, accurate estimates of the nuclear quadrupole moments are obtained. The calculated values are Q(35Cl)=-81.1(1.2) mb, Q(79Br)=302(5) mb, and Q(127I)=-680(10) mb. Currently accepted reference values [Pyykko, Mol. Phys. 99, 1617 (2001)] are -81.65(80), 313(3), and -710(10) mb, respectively. Our values are lower for the heavier halogens, corroborating the recent work of van Stralen and Visscher [Mol. Phys. 101, 2115 (2003)], who obtained Q(127I)=-696(12) mb in a series of molecular calculations.