Hydrothermal synthesis of GdPO4 in the presence of poly(methacrylic acid) yields nanorods with a diameter of 15 nm and an aspect ratio of 20. Powder X-ray diffraction patterns showed that the GdPO4 nanorods display peaks characteristics for both monoclinic and hexagonal structures. Three-dimensional electron diffraction tomography (3D EDT) was used to determine the structures ab initio on the basis of reciprocal volume reconstruction of electron diffraction data sets collected from single nanorods. The crystal structure of the monoclinic form was shown to be P21/n, corroborating previous work. We were able to solve the 3D structure of the hexagonal P6222 form, which has not been reported previously. Our work shows that 3D EDT is a powerful method that can be used for solving structures of single nanocrystals.