Merging an HD+ beam with velocity matched electrons in a heavy ion storage ring we observed rapid cooling of the rotational excitations of the HD+ ions by superelastic collisions (SEC) with the electrons. The cooling process is well described using theoretical SEC rate coefficients obtained by combining the molecular R-matrix approach with the adiabatic nuclei rotation approximation. We verify the DeltaJ=-2 SEC rate coefficients, which are predicted to be dominant as opposed to the DeltaJ=-1 rates and to amount to (1-2)x10;{-6} cm;{3} s;{-1} for initial angular momentum states with J< or =7, to within 30%.