Polydomain liquid crystalline (nematic) elastomers ave highly unusual mechanical properties, dominated by the dramatically non-linear stress-strain response that reflects stress-induced evolution of domain patterns. Here, we study the classical Hertz indentation problem in such a material. Experimentally, we find that polydomain nematic elastomers display a smaller exponent than the classical 3/2 in the load vs. indentation depth response. This is puzzling: asymptotically a softer stress-strain response requires a larger exponent at small loads. We resolve this by theory where three regimes are identified – an initial elastic regime for shallow indentation that is obscured in experiment, an intermediate regime where local domain pattern evolution leads to a smaller scaling in agreement with experiments, and a final stiffening regime where the completion of local domain evolution returns the response to elastic. This three-regime structure is universal, but the intermediate exponent is not. We discuss how our work reveals a new mechanism of enhanced adhesion for pressure-sensitive adhesion of nematic lastomers.