Aeolis Dorsa, a large sedimentary basin on Mars, contains an array of fluvially dominated sedimentary deposits. These deposits preserve a record of fluvial erosion and deposition during early Martian history. We present evidence that some of these fluvial deposits represent incised valleys carved and filled during falls and rises in base level, which were likely controlled by changes in water-surface elevation of a large lake or sea. The valley stratigraphy consists of three low-albedo, channelized corridors, each several tens of kilometers long in the streamwise direction. Deposits composing the basal valley fills are characterized by laterally amalgamated point-bar strata confined between valley walls that preserve scoop-shaped segments cut by the erosive outer banks of meandering river bends. Both the point-bar deposits and valley walls were produced by a net-erosional river system. Subsequent valley-filling deposits are defined by both channels and associated overbank strata. The stacked channel-filling deposits are sinuous in form, but unlike the basal strata, they preserve no evidence of river migration. Within each valley, there are multiple sinuous ridges ranging from a few meters to several tens of meters thick, which we interpret as channel-belt deposits that have been topographically inverted via differential erosion. Evidence for channel avulsions and reoccupations, the overall cutting and filling patterns, and consistent up-section decreases in recorded channel migration support the interpretation of the low-albedo corridors as valley stratigraphy cut and filled in the presence of a migrating backwater zone. Crosscutting valleys require at least two episodes of base-level fall and rise at >50 m per episode. These base-level cycles are consistent with the presence of an ancient large lake, sea, or ocean and its fluctuating water-surface elevation. Additionally, channel bend asymmetry preserved in channel-belt deposits indicates a southeastern flow direction.