In order to assess the sedimentological and stratigraphic history of the Melas Chasma rift basin, Mars, and investigate the possibility of past bodies of water, we have mapped Hesperian stacked sedimentary deposits containing what appear to be 10² m scale topsets, clinoforms, toesets and olistoliths located on the immediate hangingwall of a normal fault, and correlated these with folded and slumped units on the basin floor. The vertical extent of clinoforms suggest deposition in bodies of water that were tens to hundreds of metres deep associated with gravity-driven mass-movement of sediment to the basin floor. We correlated the basin margin deposits with basin-floor deposits by mapping unconformities, which define four depositional sequences. Using the principles of sequence stratigraphy in rifts, developed for terrestrial analogues in the Gulf of Corinth, Greece, we infer the history of the Melas Chasma deposits. Results suggest that water-high-stand delta deposits became stacked across unconformities in a basin undergoing active hangingwall subsidence. Assuming slip-rates on the basin-bounding normal fault similar to that found on other terrestrial and Martian faults, we infer timescales of ~1.25 to 15 million years for the sedimentation and water body. We discuss our findings in terms of a possible connection to the putative paleo-ocean on the Martian northern hemisphere.