In vivo and in vitro cells rely on the support of an underlying biocompatible substrate, such as the extracellular matrix or a culture substrate, to spread and proliferate. The mechanical and chemical properties of such structures play a central role in the dynamical and statistical properties of the tissue. At the cell scale, these substrates can be highly disordered triggering a complex biochemical response that can not only affect the single cells but also condition tissue-scale properties. We use the Self-Propelled Voronoi model to shine light on the effects of substrate disorder on the tissues’ mechanical properties. We find that when the characteristic length scale of disorder is smaller than the cell size, the tissue is less rigid than its homogeneous counterpart, with a consequent increase in cell motility. Our results also suggest that the decrease in rigidity is accompanied by a percolation transition of the cluster of fluid cells. This result is in sharp contrast to what has been reported for tissues with heterogeneity in the mechanical properties of the individual cells, where the disorder favours rigidity, offering new insights into tissue dynamics and cancer progression.