The distribution in space and time of liquid water on Mars is relevant to astrobiology and astroclimatology. To date, most orbital observations that attest to past fluvial and lacustrine activity on Mars have been dedicated to surficial landforms (i.e., drainage networks and depositional fans). Here we report an unprecedented identification of typical stratigraphic architectures made in Mars Global Surveyor Mars Orbiter Camera images of layered material in southern Melas Chasma. A particular set of strata is arranged in three depositional sequences bounded by stratigraphic unconformities. The sequences show spectacular steeply inclined clinoforms, and a broad channel-like depression. There are the same complex stratal patterns in Valles Marineris on Mars as there are in terrestrial deposits. Insights into these three-dimensional deposit geometries are used to tentatively isolate specific depositional processes and point to ancient subaqueous settings. Findings in southern Melas indicate a very attractive spot to which the search for ancient habitable environments on Mars could be directed.