The effect of pressure on the crystal structure of GaAsO4 has been studied using energy-dispersive powder diffraction up to 19.7 GPa. A structural phase transition was observed between 6.3 and 9.5 GPa from the ambient hexagonal structure to a triclinic structure. A model for this new high-pressure phase is presented. The low- and high-pressure phases were found to have bulk moduli of 17.6 and 177.0 GPa, respectively. The phase transition is reversible and first order with a volume discontinuity of 8%. The implications for the related shape-memory materials are discussed.