The label-free nature of surface plasmon resonance techniques (SPR) enables a fast, specific, and sensitive analysis of molecular interactions. However, detection of highly diluted concentrations and small molecules is still challenging. It is shown here that in contrast to continuous gold films, gold nanohole arrays can significantly improve the performance of SPR devices in angle-dependent measurement mode, as a signal amplification arises from localized surface plasmons at the nanostructures. This leads consequently to an increased sensing capability of molecules bound to the nanohole array surface. Furthermore, a reduced graphene oxide (rGO) sensor surface was layered over the nanohole array. Reduced graphene oxide is a 2D nanomaterial consisting of sp2-hybridized carbon atoms and is an attractive receptor surface for SPR as it omits any bulk phase and therefore allows fast response times. In fact, it was found that nanohole arrays demonstrated a higher shift in the resonance angle of 250–380% compared to a continuous gold film. At the same time the nanohole array structure as characterized by its diameter-to-periodicity ratio had minimal influence on the binding capacity of the sensor surface. As a simple and environmentally highly relevant model, binding of the plasticizer diethyl phthalate (DEP) via π-stacking was monitored on the rGO gold nanohole array realizing a limit of detection of as low as 20 nM. The concentration-dependent signal change was studied with the best performing rGO-modified nanohole arrays. Compared to continuous gold films a diameter-to-periodicity ratio (D/P) of 0.43 lead to a 12-fold signal enhancement. Finally, the effect of environmental waters on the sensor was evaluated using samples from sea, lake and river waters spiked with analytically relevant amounts of DEP during which significant changes in the SPR signal are observed. It is expected that this concept can be successfully transferred to enhance the sensitivity in SPR sensors.