Much historical perspective about terrestrial and marine processes can be obtained from examination of fluvial valleys formed during lower sea level on surfaces that are now continental shelves. The continental shelf near the mouth of the Fly River (Gulf of Papua) has three incised valleys, which were not extensively modified or filled during the Holocene Transgression. Multibeam mapping of the valleys documents their morphology; seismic profiling reveals stratigraphy of sediment fill; and coring within and near the valleys suggests mechanisms of filling. Kiwai Valley is deep (20–50 m relief), narrow (∼1 km wide), steep-sided and meandering, due to river flows that caused its excavation through competent sedimentary deposits. Purutu Valley is shallow (10–20 m relief) and broad (>2 km wide). Umuda Valley is widest (∼14 km) and has multiple channels with variable incision depths, suggesting more extensive fluvial activity than the other two valleys. Valley filling has occurred in several ways, reflecting valley morphology and location relative to the present river mouth. Kiwai and Umuda valleys reveal three stages of infill: (1) hemipelagic sedimentation at distal sites, (2) gravity-driven flows spreading down the valley, and (3) subsequent clinoform progradation that completely fills the valley. Purutu Valley fill is dominated by clinoform progradation. Clinoform progradation in Umuda Valley is driven by intense sediment reworking on the surrounding topset regions, and its large width allows progradation from the sides as well as down its axis. Most shelf valleys around the world were filled long ago, and available techniques have severe limitations for documenting the details of morphology and the mechanisms of filling. The shelf valleys described in this paper provide a unique perspective to terrestrial and marine processes before, during, and after the Holocene Transgression.