Quasireal photons exchanged in relativistic heavy ion interactions are powerful probes of the gluonic structure of nuclei. The coherent J=ψ photoproduction cross section in ultraperipheral lead-lead collisions is measured as a function of photon-nucleus center-of-mass energies per nucleon (WPbγN) over a wide range of 40 < WPbγN < 400 GeV. Results are obtained using data at the nucleon-nucleon center-of-mass energy of 5.02 TeV collected by the CMS experiment at the CERN LHC, corresponding to an integrated luminosity of 1.52 nb−1. The cross section is observed to rise rapidly at low WPbγN, and plateau above WPbγN ≈ 40 GeV, up to 400 GeV, entering a new regime of small Bjorken-x (≈6 × 10−5) gluons being probed in a heavy nucleus. The observed energy dependence is not predicted by current quantum chromodynamic models.