The galactic detective work found that Andromeda has eaten several smaller galaxies during the past three billion years, with left-overs found in large streams of stars.
Dr Avon Huxor, from the University of Bristol, discovered around 100 dense clusters of stars, known as 'globular clusters', around Andromeda. These have been studied by an international research team to reveal very faint traces of more small galaxies that Andromeda gobbled up several billion years ago.
Dr Dougal Mackey, from Australian National University, co-led the study with Professor Geraint Lewis from the University of Sydney.
Dr Mackey, from the ANU Research School of Astronomy and Astrophysics, said: "The Milky Way is on a collision course with Andromeda in about four billion years, so knowing what kind of a monster our galaxy is up against is useful in finding out its ultimate fate.
"Andromeda has a much bigger and more complex stellar halo than the Milky Way, which indicates that it has cannibalised many more galaxies, possibly larger ones."
The signs of ancient feasting are written in the stars orbiting Andromeda, with the team studying dense clusters of stars, known as globular clusters, to reveal the ancient mealtimes.
"By tracing the faint remains of these smaller galaxies with embedded star clusters, we've been able to recreate the way Andromeda drew them in and ultimately enveloped them at the different times," Dr Mackey said.
The discovery presents several new mysteries, with the two bouts of galactic feeding coming from completely different directions.
"This is very weird and suggests that the extragalactic meals are fed from what's known as the 'cosmic web' of matter that threads the universe," Professor Lewis said.
"More surprising is the discovery that the direction of the ancient feeding is the same as the bizarre 'plane of satellites', an unexpected alignment of dwarf galaxies orbiting Andromeda."
Dr Mackey and Professor Lewis were part of team that previously discovered such planes are fragile and rapidly destroyed by Andromeda's gravity within a few billion years.
Studying Andromeda has also informed understanding about the way our galaxy has grown and evolved over many billions of years.
The study, published in Nature, analysed data from the Pan-Andromeda Archaeological Survey (PAndAS).
Dr Huxor, who currently works in the School for Policy Studies but was based in the School of Physics at the time of this research, led the search for globular clusters and said: "I was surprised by the number and extent of globular clusters found around Andromeda. It is this that has helped us to disentangle the history of this beautiful galaxy."
The team involved institutions from Australia, New Zealand, the United Kingdom, Netherlands, Canada, France and Germany.
Paper
'Two major accretion epochs in M31 from two distinct populations of globular clusters' by D. Mackey et al in Nature.