This paper characterizes the detailed sedimentology of a fluvial sandbody on Mars for the first time and interprets its depositional processes and palaeoenvironmental setting. Despite numerous orbital observations of fluvial landforms on the surface of Mars, ground-based characterization of the sedimentology of such fluvial deposits has not previously been possible. Results from the NASA Mars Science Laboratory Curiosity rover provide an opportunity to reconstruct at fine scale the sedimentary architecture and palaeomorphology of a fluvial environment on Mars. This work describes the grain size, texture and sedimentary facies of the Shaler outcrop, reconstructs the bedding architecture, and analyses cross-stratification to determine palaeocurrents. On the basis of bedset geometry and inclination, grain-size distribution and bedform migration direction, this study concludes that the Shaler outcrop probably records the accretion of a fluvial barform. The majority of the outcrop consists of large-scale trough cross-bedding of coarse sand and granules. Palaeocurrent analyses and bedform reconstruction indicate that the beds were deposited by bedforms that migrated towards the north-east, across the surface of a bar that migrated south-east. Stacked cosets of dune cross-bedding suggest aggradation of multiple bedforms, which provides evidence for short periods of sustained flow during Shaler deposition. However, local evidence for aeolian reworking and the presence of potential desiccation cracks within the outcrop suggest that fluvial deposition may have been intermittent. The uppermost strata at Shaler are distinct in terms of texture and chemistry and are inferred to record deposition from a different sediment dispersal system with a contrasting provenance. The outcrop as a whole is a testament to the availability of liquid water on the surface of Mars in its early history.