A drop of water spreads very rapidly just after it is gently deposited on a solid surface. Here we experimentally investigate how these early stages of spreading are influenced by different types of surface complexity. In particular, we consider micro-textured substrates, chemically striped substrates and soft substrates. For all these complex substrates, it is found that there always exists an inertial regime where the radius r of the wetted area grows as r ∼ t1/2. For perfectly wetting substrates, this regime extends over several decades in time, whereas we observe a deviation from a pure power-law for partially wetting substrates. Our experiments reveal that even the cross-over from the 1/2 power law to the final equilibrium radius displays a universal dynamics. This cross-over is governed only by the final contact angle, regardless of the details of the substrate.