We argue that large fluctuations in the saturation momentum are necessary to explain the ATLAS and ALICE data on p A collisions measured at the LHC. Using a form for the distribution of fluctuations motivated by theoretical studies of the non-linear evolution equations for the Color Glass Condensate, we find a remarkably good agreement between theory and the measured distributions. If the saturation momentum fluctuates, we argue that the cross section for a proton probe should also fluctuate, consistent with previous observations.