Valley networks are some of the strongest lines of evidence for extensive fluvial activity on early (Noachian; >3.7 Ga) Mars. However, their purported absence on certain ancient terrains, such as Arabia Terra, is at variance with patterns of precipitation as predicted by “warm and wet” climate models. This disagreement has contributed to the development of an alternative “icy highlands” scenario, whereby valley networks were formed by the melting of highland ice sheets. Here, we show through regional mapping that Arabia Terra shows evidence for extensive networks of sinuous ridges. We interpret these ridge features as inverted fluvial channels that formed in the Noachian, before being subject to burial and exhumation. The inverted channels developed on extensive aggrading flood plains. As the inverted channels are both sourced in, and traverse across, Arabia Terra, their formation is inconsistent with discrete, localized sources of water, such as meltwater from highland ice sheets. Our results are instead more consistent with an early Mars that supported widespread precipitation and runoff.