Large galaxies grow through the accumulation of dwarf galaxies. In principle it is possible to trace this growth history via the properties of a galaxy’s stellar halo3. 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 disk, as are more centrally located clusters. The M31 halo also contains coherent stellar substructures, along with a smoothly distributed stellar component. 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 halo. 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 galaxies 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.