Optical materials with vanishing dielectric permittivity, known as epsilon-near-zero (ENZ) materials, have been shown to possess enhanced nonlinear optical responses in their ENZ region. These strong nonlinear optical properties have been firmly established in homogeneous materials; however, it is as of yet unclear whether metamaterials with effective optical parameters can exhibit a similar enhancement. Here, we probe an optical ENZ metamaterial composed of a subwavelength periodic stack of alternating Ag and SiO$_2$ layers and measure a nonlinear refractive index $n_2 = (1.2 pm 0.1) times 10^{-12}$ m$^2$/W and nonlinear absorption coefficient $beta = (-1.5 pm 0.2) times 10^{-5}$ m/W at its effective zero-permittivity wavelength. The measured $n_2$ is $10^7$ times larger than $n_2$ of fused silica and four times larger than that the $n_2$ of silver. We observe that the nonlinear enhancement in $n_2$ scales as $1/(n_0 mathrm{Re}[n_0])$, where $n_0$ is the linear effective refractive index. As opposed to homogeneous ENZ materials, whose optical properties are dictated by their intrinsic material properties and hence are not widely tunable, the zero-permittivity wavelength of the demonstrated metamaterials may be chosen to lie anywhere within the visible spectrum by selecting the right thicknesses of the sub-wavelength layers. Consequently, our results offer the promise of a means to design metamaterials with large nonlinearities for applications in nanophotonics at any specified optical wavelength.