Relativistic electron temperatures were measured from kilojoule, subrelativistic laser-plasma interactions. Experiments show an order of magnitude higher temperatures than expected from a ponderomotive scaling, where temperatures of up to 2.2 MeV were generated using an intensity of 1×10^{18}W/cm^{2}. Two-dimensional particle-in-cell simulations suggest that electrons gain superponderomotive energies by stochastic acceleration as they sample a large area of rapidly changing laser phase. We demonstrate that such high temperatures are possible from subrelativistic intensities by using lasers with long pulse durations and large spatial scales.