Large galaxies grow through the accumulation of dwarf galaxies1,2. In principle it is possible to trace this growth history via the properties of a galaxy's stellar halo3-5. Previous investigations of the galaxy Messier 31 (M31, Andromeda) have shown that outside a galactocentric radius of 25 kiloparsecs the population of halo globular clusters is rotating in alignment with the stellar disk6,7, as are more centrally located clusters8,9. The M31 halo also contains coherent stellar substructures, along with a smoothly distributed stellar component10-12. Many of the globular clusters outside a radius of 25 kiloparsecs are associated with the most prominent substructures, but some are part of the smooth halo13. Here we report an analysis of the kinematics of these globular clusters. We find two distinct populations rotating perpendicular to each other. The rotation axis for the population associated with the smooth halo is aligned with the rotation axis for the plane of dwarf galaxies14 that encircles M31. We interpret these separate cluster populations as arising from two major accretion epochs, probably separated by billions of years. Stellar substructures from the first epoch are gone, but those from the more recent second epoch still remain.