The Cydonia region of Mars is littered with mesas, which are an unusual geographic feature on Mars. A sample of a few of these, including the commonly known as "The Face on Mars", is shown below. How were these mesas actually constructed?
One theory is that long ago the mesas were craters that got filled with lava. Once the lava solidified, floods eroded the land around the lava trap, creating a mesa.
According to Dr. James B. Garvin, former Chief Scientist for NASA, the mesas could also have been carved by glaciers or wind, or pushed up by tectonic activity.
The problem is that we don't know yet, because we don't have enough data.