All-optical signal processing enables modulation and transmission speeds not achievable using electronics alone(1,2). However, its practical applications are limited by the inherently weak nonlinear effects that govern photon-photon interactions in conventional materials, particularly at high switching rates(3). Here, we show that the recently discovered nonlocal optical behaviour of plasmonic nanorod metamaterials(4) enables an enhanced, ultrafast, nonlinear optical response. We observe a large (80%) change of transmission through a subwavelength thick slab of metamaterial subjected to a low control light fluence of 7 mJ cm(-2), with switching frequencies in the terahertz range. We show that both the response time and the nonlinearity can be engineered by appropriate design of the metamaterial nanostructure. The use of nonlocality to enhance the nonlinear optical response of metamaterials, demonstrated here in plasmonic nanorod composites, could lead to ultrafast, low-power all-optical information processing in subwavelength-scale devices.