Clusters on surfaces are vitally important for nanotechnological applications. Clearly, cluster–surface interactions heavily influence the preferred cluster structures, compared to clusters in vacuum. Nevertheless, systematic explorations and an in-depth understanding of these interactions and how they determine the cluster structures are still lacking. Here we present an extension of our well-established non-deterministic global optimization package OGOLEM from isolated clusters to clusters on surfaces. Applying this approach to intentionally simple Lennard-Jones test systems, we produce a first systematic exploration that relates changes in cluster–surface interactions to resulting changes in adsorbed cluster structures.