The structures and properties of vanadium oxides are often related to the formation of molecule-like clusters of vanadium cations through direct V-V bonding. GaV2O4, a new vanadium spinel, was synthesized. Powder diffraction and X-ray total scattering studies, complemented by magnetization and resistivity measurements, reveal that the low-temperature phase of this material is structurally distorted and features ordered pairs of three- and four-atom vanadium clusters. These clusters persist into a disordered cubic phase above the charge-ordering transition at TCO = 415 K. Furthermore, quasi-elastic neutron scattering indicates that the disordered clusters remain well-defined and static to 1100 K.