A planet’s interior is a time capsule, preserving clues to its early history. We report the discovery of kilometer-scale heterogeneities throughout Mars’ mantle, detected seismically through pronounced wavefront distortion of energy arriving from deeply probing marsquakes. These heterogeneities, likely remnants of the planet’s formation, imply a mantle that has undergone limited mixing driven by sluggish convection. Their size and survival constrain Mars’ poorly known mantle rheology, indicating a high viscosity of 1021.3 to 1021.9 pascal-seconds and low temperature dependence, with an effective activation energy of 70 to 90 kilojoules per mole, suggesting a mantle deforming by dislocation creep. The limited mixing, coupled with ubiquitous, scale-invariant heterogeneities, reflects a highly disordered mantle, characteristic of the more primitive interior evolution of a single-plate planet, contrasting sharply with the tectonically active Earth.