Solid electrolytes have regained tremendous interest recently in light of the exposed vulnerability of current rechargeable battery technologies. While designing solid electrolytes, most efforts concentrated on creating structural disorder (vacancies, interstitials, etc.) in a cationic Li/Na sublattice to increase ionic conductivity. In phosphates, the ionic conductivity can also be increased by rotational disorder in the anionic sublattice, via a paddle-wheel mechanism. Herein, we report on Na4Zn(PO4)2 which is designed from Na3PO4, replacing Na+ with Zn2+ and introducing a vacancy for charge balance. We show that Na4Zn(PO4)2 undergoes a series of structural transitions under temperature, which are associated with an increase in ionic conductivity by several orders of magnitude. Our detailed crystallographic study, combining electron, neutron, and X-ray powder diffraction, reveals that the room-temperature form, α-Na4Zn(PO4)2, contains orientationally ordered PO4 groups, which undergo partial and full rotational disorder in the high-temperature β- and γ-polymorphs, respectively. We furthermore showed that the highly conducting γ-polymorph could be stabilized at room temperature by ball-milling, whereas the β-polymorph can be stabilized by partial substitution of Zn2+ with Ga3+ and Al3+. These findings emphasize the role of rotational disorder as an extra parameter to design new solid electrolytes.