Catchment travel time distributions reflect how precipitation from different storms is stored and mixed as it is transported to the stream. Catchment travel time distributions can be described by the mean travel time and the shape of the distribution around the mean. Whereas mean travel times have been quantified in a range of catchment studies, only rarely has the shape of the distribution been estimated. The shape of the distribution affects both the short-term and long-term catchment response to a pulse input of a soluble contaminant. Travel time distributions are usually estimated from conservative tracer concentrations in precipitation and streamflow, which are analyzed using time-domain convolution or spectral methods. Of these two approaches, spectral methods are better suited to determining the shape of the distribution. Previous spectral analyses of both rainfall and streamflow tracer time series from several catchments in Wales showed that rainfall chemistry spectra resemble white noise, whereas the stream tracer spectra in these same catchments exhibit fractal 1/f scaling over three orders of magnitude. Here we test the generality of the observed fractal scaling of streamflow chemistry, using spectral analysis of long-term tracer time series from 22 catchments in North America and Europe. We demonstrate that 1/f fractal scaling of stream chemistry is a common feature of these catchments. These observations imply that catchments typically exhibit an approximate power-law distribution of travel times, and thus retain a long memory of past inputs. The observed fractal scaling places strong constraints on possible models of catchment behavior, because it is inconsistent with the exponential travel time distributions that are predicted by simple mixing models.