The Casimir force between bodies in vacuum can be understood as arising from their interaction with an infinite number of fluctuating electromagnetic quantum vacuum modes, resulting in a complex dependence on the shape and material of the interacting objects. Becoming dominant at small separations, the force has a significant role in nanomechanics and object manipulation at the nanoscale, leading to a considerable interest in identifying structures where the Casimir interaction behaves significantly different from the well-known attractive force between parallel plates. Here we experimentally demonstrate that by nanostructuring one of the interacting metal surfaces at scales below the plasma wavelength, an unexpected regime in the Casimir force can be observed. Replacing a flat surface with a deep metallic lamellar grating with sub-100 nm features strongly suppresses the Casimir force and for large inter-surfaces separations reduces it beyond what would be expected by any existing theoretical prediction.