We present Visual Sedimentation, a new design metaphor for visualizing streaming data inspired by the geological process of sedimentation. Our work started by early experiments visualizing political Twitter streams during the French 2012 presidential elections, and social interactions during a TV show. In both cases, the positive feedback we received expressed an unexpectedly high level of engagement from users, guiding our generalization of the metaphor. This article explores Visual Sedimentation and describes a new generative design space for Information Visualization. Geological sedimentation is our inspiration as it smoothly aggregates falling objects by compacting them into strata. We use this idea to visualize changing information in a new way by providing continuity between the representation of new and older data. The metaphor preserves an overall visual encoding while making it suitable for monitoring streaming data generated at unpredictable rates.