For the spreading of a droplet covered with insoluble surfactant over an inclined random heterogeneous substrate, the base state and disturbance evolution equations for the film thickness and surfactant concentration are derived using the lubrication theory. Stability of the droplet spreading on the heterogeneous substrates, and effects of dimensionless parameters as well as the internal mechanism are investigated based on the non-modal stability theory. Results show that the disturbances of film thickness and surfactant concentration exihibit a double-hump shape and the crests lie in thinning regions at the bottom of the droplet. With increasing disturbance wave number, the stability of the droplet spreading is enhanced, but the maximal disturbance transfers from the right-side to the left-side of the droplet bottom. Increasing inclined angle leads to severe instability distinctly. Improving topographical height or increasing wave number of the substrate leads the spreading stability to firstly enhance and then to weaken. The droplet evolution displays an unstable spreading under smaller capillary number, with the maximum disturbance to be increasing before decreasing.