The gecko adhesion system fascinates biologists and materials scientists alike for its strong, reversible, glue-free, dry adhesion. Understanding the adhesion system's performance on various surfaces can give clues as to gecko behaviour, as well as towards designing synthetic adhesive mimics. Geckos encounter a variety of surfaces in their natural habitats; tropical geckos, such as Gekko gecko, encounter hard, rough tree trunks as well as soft, flexible leaves. While gecko adhesion on hard surfaces has been extensively studied, little work has been done on soft surfaces. Here, we investigate for the first time the influence of macroscale and nanoscale substrate modulus on whole animal adhesion on two different substrates (cellulose acetate and polydimethylsiloxane) in air and find that across 5 orders of magnitude in macroscale modulus, there is no change in adhesion. On the nanoscale, however, gecko adhesion is shown to depend on substrate modulus. This suggests that low surface-layer modulus may inhibit the gecko adhesion system, independent of other influencing factors such as macroscale composite modulus and surface energy. Understanding the limits of gecko adhesion is vital for clarifying adhesive mechanisms and in the design of synthetic adhesives for soft substrates (including for biomedical applications and wearable electronics).