There is evidence that a subset of fluvial deposits at Aeolis Dorsa, a basin on Mars, preserve incised valleys carved and filled during changes in base level, which was likely controlled by water surface elevation of a large lake or sea. Three low-albedo, channelized corridors, each several tens of kilometers long, contain relict point bars and scooped boundaries at their bases, indicating that the base and lateral extent of each corridor was defined by a migrating, net-erosional river. Above the basal deposits are stacks several tens of meters thick of “inverted sinuous ridges”, which are channel-filling deposits that have been exhumed and topographically inverted. Indicators of avulsions, channel re-occupations, an overall flattening of basal topography, and confinement of inverted sinuous ridges to the dark corridors are evidence of the gradual filling of a valley cut by the basal migrating river. Valley incision and fill are common responses to sea level change on Earth. Aeolis Dorsa is currently open to the northern lowlands of Mars, where an ocean has been hypothesized to have once existed, although a large lake could have also controlled base level. Cross-cutting valleys require at least two episodes of base level fall and rise. The magnitudes of the base level changes are estimated at about 80 meters, based on the thickness of the valley-filling stratigraphy. Meander asymmetry is consistent with a southeastern flow direction, and is supported by a set of branching fluvial deposits 40 km to the southeast which, qualitatively, appear to be deltaic in origin. / text