Large outflow channels on ancient terrains of Mars have been interpreted as the products of catastrophic flood events. The rapid burial of water-rich sediments after such flooding could have led to sedimentary volcanism, in which mixtures of sediment and water (mud) erupt to the surface. Tens of thousands of volcano-like landforms populate the northern lowlands and other local sedimentary depocentres on Mars. However, it is difficult to determine whether the edifices are related to igneous or mud extrusions, partly because the behaviour of extruded mud under Martian surface conditions is poorly constrained. Here we investigate the mechanisms of mud propagation on Mars using experiments performed inside a low-pressure chamber at cold temperatures. We found that low viscosity mud under Martian conditions propagates differently from that on Earth, because of a rapid freezing and the formation of an icy crust. Instead, the experimental mud flows propagate like terrestrial pahoehoe lava flows, with liquid mud spilling from ruptures in the frozen crust, and then refreezing to form a new flow lobe. We suggest that mud volcanism can explain the formation of some lava-like flow morphologies on Mars, and that similar processes may apply to cryovolcanic extrusions on icy bodies in the Solar System.