Twelve million years ago the Fendahl came to Earth, "taking in Mars on the way. That's why it's a dead planet" says the Fourth Doctor in Image of the Fendahl. We may infer that he overestimated its destructive influence; certainly it isn't until after his fifth incarnation that we are able to piece together something of a history of Mars' indigenous people.
Martian society dates back well over two million years, but is older than the culture and reign of the Ice Warriors themselves. For twelve thousand years, Martian civilisation is a technologically sophisticated and peaceful one, pre-existing the term 'warrior' and comprised of artisans, farmers and builders of a network of canals and pyramids. Though crime existed (there are beadles and magistrates such as Isskar), their strong belief in honour was inherent in their gift economy (The Judgement of Isskar). After a gravity well is created by the removal of a segment of the Key to Time from the planet, thirty years of climatic and tectonic upheaval followed, changing the face and environment of Mars utterly. The first of what appears to be a long and periodic exodus from Mars begins around this point, but the main population retreats underground and later emerges ignorant of the extent of the damage until Ice Lord Izdaal faces his certain death by the Red Dawn and proves the apparent calamity. His sacrifice saves his people, and the Fifth Dynasty sees ice tombs created on Deimos to preserve Martian civilisation for the ages, ordained by Izdaal and designed by Lord Vasslor (Deimos). At the same time a period of prolonged war reigns and a militaristic Ice Warrior culture emerges. During this time a group of Ice Warriors led by Lord Arakssor are declared war criminals and imprisoned on the Antarctic continent of Earth (Frozen Time). Further exploration attempts to other worlds are also attempted: no earlier than twelve thousand years ago Varga's ship is trapped on Earth during the first ice age (Arden's comments in The Ice Warriors specifically refer to 'pre-historic' and 'pre-Viking' times, our inference being beyond Clent's earlier "5000 years of history" line.)
Around the 8th millennium BC the last flowers on Mars become extinct (The Waters of Mars), while the Ice Warriors slip further into civil war for their remaining resources. One thousand years BC the Ice Army of Marshall Sezhyr is routed - many of his followers are chained to the planet's surface to face the Red Dawn, and after the Marshall's death Hhesh and seven 'old Warriors' flee the planet and in desperation find their way to Earth (Thin Ice). With Earth now deemed uninhabitable the Martians people complete their exodus, retreating to closer shelters including the nearby asteroid belt (the Ice Lords entombed within Deimos are ignorant of the asteroid belt ice tombs suggesting they are indeed an earlier party). Certainly by the 20th century Mars is empty; in 1929 Arakssor is unable to make contact and assumes the great exodus had already occurred, while the awakened Hhesh and his compatriots thaw out in 1946, attempting to contact their home world to no avail.
By the early 21st century Martian refugees have meanwhile settled outside the solar system, although still maintain some surveillance of their home world, picking up Arakksor's transmissions and travelling there using hyperdrive. By later in the same century the Warriors return to the Solar System temporarily, using the "dying" Mars as a base in a doomed attempt to transform and conquer Earth (given the motives behind Slaar's mission we might infer that long-term sustainability is still out of reach for a large population on Mars.)
By the 23rd century (Mission to Magnus, Deimos) the Ice Warriors have developed what the Doctor considers to be a vast space empire, although he confesses to having thought them extinct, suggesting a sort of miraculous Martian revival around this point. Survivors from the Solar System's asteroid belt eventually reach, conquer, and colonise the planet Halcyon by the 31st century, renaming it New Mars.