Tetragonal scheelite-type CaWO4 nanocrystals recently prepared by a hydrothermal method show an enhancement of its structural symmetry with the decrease in nanocrystal size. The analysis of the volume dependence of the structural parameters in CaWO4 nanocrystals with the help of ab initio total-energy calculations shows that the enhancement of the symmetry in the scheelite-type nanocrystals is a consequence of the negative pressure exerted on the nanocrystals; i.e., the nanocrystals are under tension. Besides, the behavior of the structural parameters in CaWO4 nanocrystals for sizes below 10 nm suggests an onset of a scheelite-to-zircon phase transformation in good agreement with the predictions from our ab initio calculations. CaWO4 nanocrystals exhibit a reconstructive-type mechanism for the scheelite-to-zircon phase transition that seems to follow the tetragonal path that links both structures. This result is in contrast with the mechanism recently proposed for this transition in bulk ZrSiO4 where the transition goes through an intermediate monoclinic phase.