Ice stream bed topography contains key evidence for the ways ice streams interact with, and are potentially controlled by, their beds. Here we present the first application of two-dimensional Fourier analysis to 22 marine and terrestrial topographies from 5 regions in Antarctica and Canada, with and without mega-scale glacial lineations (MSGLs). We find that the topography of MSGL-rich ice stream sedimentary beds is characterized by multiple, periodic wavelengths between 300 and 1200 m and amplitudes from decimeters to a few meters. This periodic topography is consistent with the idea that instability is a key element to the formation of MSGL bedforms. Dominant wavelengths vary among locations and, on one paleo ice stream bed, increase along the direction of ice flow by 1.7 ± 0.52% km−1. We suggest that these changes are likely to reflect pattern evolution via downstream wavelength coarsening, even under potentially steady ice stream geometry and flow conditions. The amplitude of MSGLs is smaller than that of other fluvial and glacial topographies but within the same order of magnitude. However, MSGLs are a striking component of ice stream beds because the topographic amplitude of features not aligned with ice flow is reduced by an order of magnitude relative to those oriented with the flow direction. This study represents the first attempt to automatically derive the spectral signatures of MSGLs. It highlights the plausibility of identifying these landform assemblages using automated techniques and provides a benchmark for numerical models of ice stream flow and subglacial landscape evolution.