Gullies are a class of geologically recent landform on Mars that show evidence of downslope transport of sedimentary material from recessed alcoves, through incised channels, to distributary fans or aprons. The mechanisms invoked to account for the formation of gullies on Mars range from completely dry, granular flows or landslides, to debris flows that incorporate some component of liquid water, to fluvial erosion and alluvial-fan-like deposition. Each of these processes requires different amounts of liquid water, and produces different characteristic morphologies. We report on the identification of unusual lobate structures present in proximity to gullies in Protonilus Mensae. The lobes are up to ~ 3 m thick and terminate in rounded snouts. These lobate structures are present mostly downslope of gullies, and can be traced upslope through channels, to gully fan termini, and in places, onto gully fan surfaces. Crater dating indicates that the deposits formed recently—potentially within the past ~ 500 ka. We use HRSC digital elevation models to constrain mechanical properties of the lobate deposits, and to compare their formation environment to that of typical martian gullies. The Protonilus Mensae lobate deposits are interpreted to indicate local dominance of wet debris flows in the formation of the observed gullies and lobes. These observations are consistent with 1) top-down melting of the ice component of the latitude-dependent mantle terrain in which the gullies form and 2) initiation of debris flows by mobilization of the dusty lithic component of the mantle. The suite of morphological observations diagnostic of wet debris flow processes suggests the identification of an unusual environment in which the wet debris-flow formational end-member is locally the dominant gully forming process; elsewhere on Mars gully morphology may be more consistent with a range of other water-related sediment transport mechanisms including fluvial erosion, hyperconcentrated flow, and low-strength mudflows (that deposit as fans rather than lobes). These results suggest that 1) gully-forming processes involve liquid water, 2) that the water source is associated with the martian latitude-dependent mantle, and 3) that a range of water-related sediment transport processes is involved in gully formation.