We study the crystals structure and stability of four possible polymorphs of HgCl2 using first principles density functional theory. Mercury (II) halides are a unique class of materials which, depending on the halide species, form in a wide range of crystal structures, ranging from densely packed solids to layered materials and molecular solids. Predicting the groundstate structure of any member of this group from first principles, therefore, requires a general purpose functional that treats van der Waals bonding and covalent/ionic bonding adequately. Here, we demonstrate that the non-local van der Waals density functional paired with the C09 exchange functional meets this bar for HgCl2. In particular, this functional is able to predict the correct groundstate among the structures tested as well as having extremely good agreement with the experimentally known crystal structure. These results highlight the maturity of this functional and open the door to using this method for truly first principles crystal structure predictions.