Recent observations have revealed streams of gas and stars in the halo of the Milky Way that are the debris from interactions between our Galaxy and some of its dwarf companion galaxies; the Sagittarius dwarf galaxy and the Magellanic clouds. Analysis of the material has shown that much of the halo is made up of cannibalized satellite galaxies, and that dark matter is distributed nearly spherically in the Milky Way. It remains unclear, however, whether cannibalized substructures are as common in the haloes of galaxies as predicted by galaxy-formation theory. Here we report the discovery of a giant stream of metal-rich stars within the halo of the nearest large galaxy, M31 (the Andromeda galaxy). The source of this stream could be the dwarf galaxies M32 and NGC205, which are close companions of M31 and which may have lost a substantial number of stars owing to tidal interactions. The results demonstrate that the epoch of galaxy building still continues, albeit at a modest rate, and that tidal streams may be a generic feature of galaxy haloes.